Solution

Let

\[C_i = B_i-A_i.\]

The initial answer is \(\sum A_i\). If card \(i\) is flipped in the current state, the answer changes by \(C_i\); after that, its contribution becomes \(-C_i\).

Thus, one operation on \([l,r]\) adds

\[\sum_{i=l}^{r} C_i\]

to the answer and negates every \(C_i\) in this interval.

Therefore, we use the following greedy algorithm:

Repeatedly choose a maximum-sum subarray, add its sum to the answer, and negate the subarray.

We stop after \(K\) iterations, or earlier if the maximum subarray sum is non-positive.

Proof of correctness

For an array \(C\), let \(\mathrm{OPT}_k(C)\) be the maximum gain obtainable using at most \(k\) operations.

A sequence of at most \(k\) interval flips is equivalent to choosing a union of at most \(k\) disjoint intervals: a position is selected exactly when it is flipped an odd number of times. Hence, \(\mathrm{OPT}_k(C)\) is the maximum sum of at most \(k\) disjoint subarrays.

Let \(I=[l,r]\) be a maximum-sum subarray, let

\[M=\sum_{i\in I} C_i,\]

and let \(C'\) be obtained by negating \(C_i\) for \(i\in I\). We claim that

\[\mathrm{OPT}_k(C)=M+\mathrm{OPT}_{k-1}(C').\]

First, for any union \(T\) of at most \(k-1\) intervals, \(T\triangle I\) is a union of at most \(k\) intervals, where \(\triangle\) denotes symmetric difference. Moreover,

\[\sum_{i\in T\triangle I} C_i = M+\sum_{i\in T} C'_i.\]

Therefore,

\[\mathrm{OPT}_k(C)\ge M+\mathrm{OPT}_{k-1}(C').\]

For the opposite direction, take an optimal union \(S\) of at most \(k\) intervals. Since \(I\) is a maximum-sum subarray,

• every prefix and suffix of \(I\) has non-negative sum;
• every interval directly extending \(I\) to the left or right has non-positive sum.

Using these facts, we may modify \(S\) without decreasing its sum or increasing its number of components so that both ends of \(I\) are boundaries of \(S\): extend selected parts inside \(I\) to the ends of \(I\), and remove selected parts extending outside \(I\). If \(S\cap I\) is empty, insert \(I\) instead; if this creates one extra component, remove any old component, whose sum is at most \(M\).

Now \(S\triangle I\) has one fewer component, so it is a union of at most \(k-1\) intervals. Also,

\[\sum_{i\in S} C_i = M+\sum_{i\in S\triangle I} C'_i.\]

Thus,

\[\mathrm{OPT}_k(C)\le M+\mathrm{OPT}_{k-1}(C').\]

The claim follows. Applying it repeatedly proves that choosing a current maximum-sum subarray in every iteration is optimal.

Algorithm

1. Set \(C_i=B_i-A_i\) and initialize the answer with \(\sum A_i\).
2. Repeat at most \(K\) times:
   • find a maximum-sum subarray using Kadane’s algorithm;
   • stop if its sum is non-positive;
   • add its sum to the answer;
   • negate every element in the chosen subarray.
3. Output the answer.

Complexity

Each iteration takes \(O(N)\) time, so the total time complexity is

\[O(NK).\]

The space complexity is \(O(N)\).

https://atcoder.jp/contests/abc466/submissions/77424442