Penguin Food

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.2s
Memory limit: 128M

Authors:
Problem type

Peng the Penguin has hired a chef to cook N dishes for him daily. Peng assigns a value A_i to each dish, which represents how much satisfaction he gains from that dish. If he really hates the dish, he will assign it a negative number. He wants to gain the most satisfaction possible, but he can only eat a consecutive portion of the meal because he's Peng. He needs someone to write a program to help him determine the maximum amount of satisfaction he can gain daily for M days. Furthermore, the chef will only change one dish per day so he doesn't run out of ideas for dishes. The new dish can have the same satisfaction level as the previous one. Note that if the satisfaction Peng can gain by taking any consecutive portion of the meal is negative, he can choose to not take any portion and gain 0 satisfaction as a result.

Input Format

An integer N, followed by N integers on the next line, with the ith integer representing A_i.

This is followed by an integer M, followed by M lines containing two integers each, x and y, where the x^\text{th} dish (0-indexed) now has y satisfaction value.

Output Format

M+1 integers on separate lines, with the ith integer representing the maximum satisfaction Peng can obtain on day i.

Constraints

For all subtasks:

|A_i| \le 10^4

Subtask 1 [15%]

1 \le N, M \le 100

Subtask 2 [50%]

1 \le N, M \le 10^4

Subtask 3 [35%]

1 \le N, M \le 10^6

Sample Input

5
3 -4 2 5 1
3
1 1
2 -6
1 -3

Sample Output

8
12
6
6

Explanation for Sample Output

On the 1st day, the dishes were 3 -4 2 5 1, and Peng will pick 2 5 1.

On the 2nd day, the dishes were 3 1 2 5 1, and Peng eats everything.

On the 3rd day, the dishes were 3 1 -6 5 1, and Peng will pick 5 1.

On the 4th day, the dishes were 3 -3 -6 5 1, and Peng will pick 5 1.


Comments


  • -61
    Tzak  commented on Sept. 27, 2019, 8:44 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.