HCI '16 - Penguin Food - DMOJ: Modern Online Judge

HCI '16 - Penguin Food

View as PDF

Submit solution

All submissions

Best submissions

Points: 15 (partial)

Time limit: 1.2s

Memory limit: 128M

Authors:

zj97, damian, fanpu

Problem type

Peng the Penguin has hired a chef to cook $N$ $N$ dishes for him daily. Peng assigns a value $A_i$ $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$ $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$ $0$ satisfaction as a result.

Input Specification

An integer $N$ $N$ , followed by $N$ $N$ integers on the next line, with the $i^\text{th}$ $i^{th}$ integer representing $A_i$ $A_{i}$ .

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

Output Specification

$M+1$ $M + 1$ integers on separate lines, with the $i^\text{th}$ $i^{th}$ integer representing the maximum satisfaction Peng can obtain on day $i$ $i$ .

Constraints

For all subtasks:

$|A_i| \le 10^4$ $| A_{i} | \leq 10^{4}$

Subtask 1 [15%]

$1 \le N, M \le 100$ $1 \leq N, M \leq 100$

Subtask 2 [50%]

$1 \le N, M \le 10^4$ $1 \leq N, M \leq 10^{4}$

Subtask 3 [35%]

$1 \le N, M \le 10^6$ $1 \leq N, M \leq 10^{6}$

Sample Input

Copy

Sample Output

Copy

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

-66

Tzak commented on Sept. 28, 2019, 12:44 a.m. ← edited →

Although $|A_i| \le 10^4$ $| A_{i} | \leq 10^{4}$ and $N \le 10^6$ $N \leq 10^{6}$ suggests a upper bound of $10^{10}$ $10^{10}$ in a range sum, you might find it helpful to know that I had no problems with using int instead of long long.

This comment is hidden due to too much negative feedback. Show it anyway.