P16541 [EGOI 2026] Biscuits / Biscuits

Aurora and Bianca really like Italian almond biscuits. Today, their grandfather baked a huge pile of biscuits (forming a stack). To split these biscuits, they invented the following game. As long as there are biscuits left in the stack, they repeat the following steps: + Aurora chooses an integer $X \geq 0$. + Next, Bianca chooses an integer $Y \geq 0$ such that: - there are at least $Y$ biscuits remaining, and - $Y \neq X$. + Then Aurora eats the top $Y$ biscuits (if $Y=0$, she eats none). + Finally, if there are still biscuits remaining, Bianca eats the top one. Of course, both girls want to eat as much as possible. Each biscuit in the stack has a weight $1 \leq W_i \leq 50$. After all biscuits have been eaten, each person’s **happiness** equals the total weight of all biscuits she ate during the game. Both girls know how to play this game optimally—each person always makes the choice that maximizes her own final happiness. Because this game is so fun, they now play it every day. Over the next $Q$ days, their grandfather bakes the same number of biscuits each day. To make the game more interesting, each day he changes the weight of exactly one biscuit, while all other biscuit weights stay the same. For the initial stack of biscuits, and after each day’s change, you need to compute **Bianca’s happiness** at the end of the game for that day.

The first line contains two integers $N$ and $Q$, the number of biscuits and the number of changes. The biscuits are numbered from top to bottom as $0$ to $N-1$. The second line contains $N$ integers $W_0, W_1, \dots, W_{N-1}$, the initial weights of the biscuits. The next $Q$ lines describe the changes. The $i$-th line contains two integers $P_i$ and $Z_i$, meaning that the grandfather changes the weight of biscuit $P_i$ to $Z_i$. In other words, the value of $W_{P_i}$ becomes $Z_i$.

Output $Q + 1$ integers, Bianca’s happiness after the game ends each day.

### Sample Explanation **The first sample.** On the first day, the biscuit weights are $10$ and $15$. - It is optimal for Aurora to choose $X=1$. Then, Bianca chooses $Y = 0$ and eats the top biscuit. - In the second round, Aurora chooses $X = 0$. Bianca’s only choice is $Y=1$. Then Aurora eats the biscuit of weight $15$, and the game ends. On the second day, the weight of biscuit $1$ becomes $1$, so the weights are $[10, 1]$. - It is optimal for Aurora to choose $X=0$. Then, Bianca chooses $Y = 1$. Aurora eats the top biscuit, and Bianca eats the remaining one. After the game ends, Bianca’s happiness is $1$. **The second sample.** Initially, from top to bottom the biscuit weights are $[1,1,1,1,2]$. - It is optimal for Aurora to choose $X = 0$. Bianca chooses $Y = 1$. Aurora eats the first biscuit, and Bianca eats the second. - In the next round, Aurora chooses $X = 0$. Bianca chooses $Y = 2$. Aurora eats the next two biscuits, and Bianca eats the last one. When the game ends, Bianca’s total happiness is $3$. After the first change, the weights become $[1,1,20,1,2]$. - Now it is optimal for Aurora to choose $X=2$. (If she chooses any other value, Bianca will choose $Y = 2$, and then Aurora will not be able to eat that big biscuit in the middle.) In response to Aurora’s choice, Bianca chooses $Y = 0$ and eats the first biscuit. The remaining biscuit weights are $[1,20,1,2]$. - In the second round, Aurora chooses $X = 1$, and Bianca chooses $Y = 0$. Bianca again eats the top biscuit. After that, the remaining biscuit weights are $[20,1,2]$. - In the third round, Aurora chooses $X=0$. Bianca chooses $Y = 2$. Then Aurora eats the biscuits of weights $20$ and $1$, and finally Bianca eats the last biscuit of weight $2$. The total weight Bianca eats is $1+1+2 = 4$. After the second change, the weights become $[1,1,20,30,2]$. If both girls play with optimal strategies, Bianca will eat all biscuits except the one with weight $30$. ### Constraints - $2 \leq N \leq 100\ 000$. - $0 \leq Q \leq 100\ 000$. - $1 \leq W_i \leq 50$ (yes, Italian almond biscuits are light!). - $0 \leq P_i \leq N-1$ and $1 \leq Z_i \leq 50$. ### Scoring Your program will be tested on testdata split into several subtasks. To get the score for a subtask, you must solve all testdata in that subtask correctly. - **Subtask 0** [$0$ points]: Samples. - **Subtask 1** [$8$ points]: $Q = 0$ and $W_i = 1$. - **Subtask 2** [$9$ points]: $N \le 3, Q \le 5$. - **Subtask 3** [$11$ points]: At all times, the biscuit weights $W_i$ are non-increasing; in other words, $W_0 \ge W_1 \ge ... \ge W_{N-1}$. - **Subtask 4** [$13$ points]: $N \le 100, Q \le 50$. - **Subtask 5** [$18$ points]: $N \le 20\,000, Q \le 50$. - **Subtask 6** [$12$ points]: $N \le 20\,000, Q \le 5000$. - **Subtask 7** [$29$ points]: No additional constraints. Translated by ChatGPT 5