Subtask 1

For subtask 1, we can represent any game state by a bitmask of untaken coins and perform exponential-time dynamic programming.

Time complexity: ~\mathcal{O}(N \cdot 2^N)~

Subtasks 2, 3

For subtask 2 and 3, note that after the first turns by players ~A~ and ~B~, the row of coins is split into two (or less) smaller rows of coins that are effectively independent for future turns. Thus we can use dynamic programming where the state ~dp[l][r]~ represents the maximum sum ~A~ can obtain on the subarray ~[l,r]~ of coins assuming none of these coins are taken and it is currently ~A~'s turn. The transitions consider each coin in ~[l,r]~ for the next coin ~A~ takes and the two (or less) possibilities for which coin ~B~ takes immediately after.

This dynamic programming naturally computes the answer for each prefix of the final row of coins, allowing us to solve the problem in ~\mathcal{O}((N+Q)^3)~. Subtask 2 was created to reward any cubic time solutions that do not naturally compute the answer for each prefix.

Time complexity: ~\mathcal{O}((N+Q)^3)~

Subtasks 4, 5

For subtask 4 and 5, there is a conjecture we can make to get rid of an ~\mathcal{O}(N)~ factor. It turns out that one optimal move for ~A~ is to take any maximum element of the current row, which we will prove in the analysis for the final subtask. This means that if we precompute subarray maximums we only have to consider one transition from each ~dp[l][r]~ state, allowing us to solve the problem in quadratic time.

Alternatively, we can conjecture that the optimal decision points are monotonic and use Knuth's optimization, which passes all the tests if well implemented.

Similarly, subtask 4 was created to reward any quadratic time solutions that do not naturally compute the answer for each prefix.

Remark: The optimal strategy for ~B~ does not always take the maximum element possible (consider a case like ~[6,8,9,7]~ after ~A~ takes the ~9~ for example).

Time complexity: ~\mathcal{O}((N+Q)^2)~

Subtask 6

Subtask 6 was created to reward any better than quadratic time solutions that do not naturally compute the answer for each prefix. One such solution that does not require any new observations is described below.

We can precompute a sparse table that allows us to query the location of the maximum element in any subarray in ~\mathcal{O}(1)~. Then, we can do the same dynamic programming as subtask 5, except we do it recursively (with memoization) so only intervals we need are computed (with the help of the sparse table). It turns out that this solution visits only ~\mathcal{O}(N)~ states and is thus ~\mathcal{O}(N \log N)~. Consider the Cartesian tree of the array. Any node in the Cartesian tree corresponds to a maximal interval ~[l,r]~ where that number is the maximum. We can verify that any state visited during this dynamic programming is of the form ~[l+(0 \text{ or } 1),r-(0 \text{ or } 1)]~ for some such interval ~[l,r]~, which is ~\mathcal{O}(N)~ states as claimed.

Unfortunately, this solution runs in quadratic time on some subtask 7 cases such as a decreasing final row, but it is fast enough for subtask 6.

Time complexity: ~\mathcal{O}(N \log N)~

Subtask 7

To solve subtask 7, we need to abandon interval dynamic programming and use a completely different approach.

Let's consider some possible families of strategies for player ~B~. Suppose there are two very large elements right next to each other. In this case, ~B~ can guarantee that he gets at least one of these elements by always taking the other as soon as ~A~ takes one of them. This suggests that player ~B~ should pair together some pairs of adjacent elements such that no element is in more than one pair, so that he can guarantee that he gets at least the smaller element in each pair by a similar argument. In order to maximize this, ~B~ should use the maximum matching on the path graph with ~N~ nodes where the weight of the edge connecting ~i~ and ~i+1~ is ~\min(a_i,a_{i+1})~. This gives a strategy that guarantees ~B~ won't get worse than this value, now we prove that ~B~ cannot do better by giving a strategy for ~A~.

On the other hand, ~A~ can (as described before) always take some maximum element of the array. Consider the pairs of adjacent elements where ~B~ takes one of the elements right after ~A~ takes the other in any possible strategy for ~B~ against this strategy by ~A~. In each of these pairs, ~B~ gets only the smaller element since ~A~ ensures that he took the larger element, so these pairs correspond to some matching of the path graph described above. Clearly, this matching cannot be better than the maximum matching on this graph, so ~B~ cannot do better against this strategy by ~A~.

Thus we simply need to compute this maximum matching for each prefix of the final row of coins. We can do this by an easy prefix dynamic programming. The final code is very short if done properly.

Time complexity: ~\mathcal{O}(N+Q)~