Annoying Game

The annoying part of the game is that it looks like $k$ turns matter. They basically don't. Only the parity matters. Classic Codeforces behavior: huge $k$, tiny idea.

Let $M(x)$ be the maximum non-empty subarray sum of array $x$.

First, notice a simple monotonicity fact:

• If you increase some element, $M$ cannot decrease.
• If you decrease some element, $M$ cannot increase.

So Alice never needs to subtract, and Bob never needs to add. Operations also commute, because only the final array matters.

Even number of turns

Suppose $k = 2m$. Alice makes $m$ moves and Bob makes $m$ moves.

Bob has an easy upper-bound strategy: after every Alice move at index $i$, Bob plays the opposite move at the same index. After every pair of moves, the array is back where it started. So Bob can guarantee the final score is at most

$M(a).$

Now we need to show Alice can guarantee at least $M(a)$, otherwise Bob might do even better.

Take a maximum-sum subarray $S$ of the original array $a$. Let $p$ be an index in $S$ with maximum $b_p$ among all indices in $S$.

Alice plays index $p$ every time. Bob has $m$ moves. Any Bob move outside $S$ does not affect the sum of $S$. Any Bob move inside $S$ subtracts at most $b_p$, because $b_p$ was the maximum inside $S$.

Alice adds $m \cdot b_p$ to $S$, while Bob can remove at most $m \cdot b_p$ from $S$. Therefore the final sum of $S$ is at least its original sum, which is $M(a)$.

So for even $k$:

$\boxed{\text{answer} = M(a)}$

Odd number of turns

Now suppose $k = 2m + 1$. Alice has one extra move.

Bob can cancel Alice's first $m$ moves. After that, Alice gets exactly one uncanceled move. So the final array is no better for Alice than taking the original array and adding $b_i$ to one chosen index $i$.

If the final maximum subarray is $S$, and Alice's uncanceled bonus lies inside $S$, its value is

$\sum_{i\in S} a_i + b_p$

for some $p \in S$. Alice would choose the best possible $p$, so for a fixed $S$ the best bonus is $\max_{p\in S} b_p$.

Thus Bob can hold Alice to at most

$G = \max_{S \ne \emptyset}\left(\sum_{i\in S} a_i + \max_{i\in S} b_i\right).$

Again, prove Alice can actually guarantee this.

Pick a subarray $S$ that attains $G$, and let $p$ be an index in $S$ with maximum $b_p$. Alice plays index $p$ on every one of her $m+1$ turns.

Bob has only $m$ moves. Inside $S$, each Bob subtraction removes at most $b_p$. Therefore the final sum of $S$ is at least

$\sum_{i\in S} a_i + (m+1)b_p - mb_p = \sum_{i\in S} a_i + b_p = G.$

So for odd $k$:

$\boxed{\text{answer} = \max_S(\sum_{i\in S} a_i + \max_{i\in S} b_i)}$

Important trap: this is not Kadane on $a_i+b_i$. That would add every $b_i$ in a subarray, which is illegal. Alice only has one uncanceled bonus, not a coupon for the whole damn segment.

Computing the odd case

Scan left to right with two DP states:

• $dp0$: best sum of a subarray ending at the current index with no bonus used.
• $dp1$: best value of a subarray ending at the current index with exactly one $b$ bonus used.

For index $i$:

$dp0' = \max(a_i, dp0 + a_i)$

For $dp1$, there are three choices:

• start a new subarray at $i$ and use the bonus here: $a_i+b_i$
• extend a no-bonus subarray and use the bonus here: $dp0+a_i+b_i$
• extend an already-bonused subarray: $dp1+a_i$

So:

$dp1' = \max(a_i+b_i, dp0+a_i+b_i, dp1+a_i)$

The odd answer is the maximum $dp1$ seen.

The even answer is just standard Kadane on $a$.

Complexity is $O(n)$ per test case and $O(1)$ extra memory besides the input arrays. The total $n$ is $2\cdot 10^5$, so this is easily fine.