Overview

We analyze a two-player game where players take cards from either the left or right end, assuming both players play optimally, and determine the final scores of Takahashi and Aoki.

Analysis

The state of this game is fully determined by the “currently remaining interval (contiguous subsequence).”
However, since each turn branches into 2 choices (left/right), a naive exhaustive search would have up to \(2^N\) branches, which is far too slow for \(N \le 3000\).

The key insight is that the objective is to maximize “(my score) − (opponent’s score)”.
By focusing on this “difference,” we can use the following property:

• Suppose the interval \([l, r]\) remains and the “current player” is about to move:
  • If they take the left end \(A_l\), the current player gains \(A_l\)
  • Then the opponent plays optimally on the interval \([l+1, r]\), maximizing the difference (opponent − current player)
• Therefore, the difference from the current player’s perspective (current − other) is the maximum of:
  • Taking left: \(A_l - \text{dp}[l+1][r]\)
  • Taking right: \(A_r - \text{dp}[l][r-1]\) (The key point is that “the next turn is the opponent’s,” so the difference is subtracted.)

By formulating the DP in terms of “difference,” we can solve the problem without explicitly tracking whose turn it is or the parity of turns.

Furthermore, while we ultimately want the actual scores of both players, if we let \(S=\sum A_i\) be the total sum and \(D=(\text{Takahashi} - \text{Aoki})\) be the final difference, then: - \(\text{Takahashi} + \text{Aoki} = S\) - \(\text{Takahashi} - \text{Aoki} = D\)

From which: - \(\text{Takahashi} = \dfrac{S + D}{2}\), \(\text{Aoki} = S - \text{Takahashi}\)

This always divides evenly (since \(S\) and \(D\) have the same parity).

Algorithm

1. DP Definition

We consider an interval DP.

• \(\text{dp}[l][r]\): When the cards in interval \([l, r]\) remain and the “next player to take (current)” plays optimally,
  the maximum value of (current’s score) − (other’s score)

2. Transition

For interval \([l, r]\), the current player can choose one card from either end:

• Take the left end: gain \(A_l\), remaining interval is \([l+1, r]\)
  Since the next turn is the opponent’s, the opponent gains an advantage of \(\text{dp}[l+1][r]\) from their perspective.
  Therefore, the difference from the current player’s perspective is
  $\( A_l - \text{dp}[l+1][r] \)$

• Take the right end: similarly
  $\( A_r - \text{dp}[l][r-1] \)$

Thus: $\( \text{dp}[l][r] = \max\left(A_l - \text{dp}[l+1][r],\; A_r - \text{dp}[l][r-1]\right) \)$

3. Base Case

For intervals of length 1, there is only one card to take: $\( \text{dp}[i][i] = A_i \)$

4. Compression to 1D

In the implementation, \(\text{dp}[l][r]\) is computed by “extending the interval length,” and we only need: - \(\text{dp}[l+1][r]\) (same length with \(l\) incremented by 1) - \(\text{dp}[l][r-1]\) (interval one step shorter)

The provided code: - Stores \(\text{dp}[l][r]\) for the current length in a 1D array dp[l] - Updates dp[l] while increasing the length from 2, 3, …

This reduces memory to \(O(N)\).

5. Score Recovery

Ultimately, dp[0] is the difference \(D\) for the interval \([0, N-1]\).
Using the total sum \(S\): $\( \text{Takahashi}=\frac{S+D}{2},\quad \text{Aoki}=S-\text{Takahashi} \)$ and output the result.

Complexity

• Time complexity: \(O(N^2)\) (approximately \(N^2/2\) intervals)
• Space complexity: \(O(N)\) (1D DP)

Implementation Notes

• By storing the DP as “difference (current − other),” transitions can be written without worrying about turn parity.

• In the 1D compression, the update order is important. The provided code uses the form “fix the interval length and increase the left endpoint \(l\),” which ensures that dp[l+1] and the (pre-update) dp[l] are referenced correctly.

• Values can be up to \(10^9\) and \(N=3000\), so the total can reach around \(3\times 10^{12}\), but since Python integers have arbitrary precision, there is no concern about overflow.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1+n]))
    s = sum(a)

    dp = a[:]  # dp[l] = best (current - other) for interval [l..r] of current length
    for length in range(2, n + 1):
        end = n - length
        for l in range(end + 1):
            r = l + length - 1
            left = a[l] - dp[l + 1]
            right = a[r] - dp[l]
            dp[l] = left if left > right else right

    d = dp[0]
    takahashi = (s + d) // 2
    aoki = s - takahashi
    sys.stdout.write(f"{takahashi} {aoki}")

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.