Overview

\(N\) cards are arranged in a row, and two players alternately take a card from either the left end or the right end. We use interval DP to determine each player’s score when both players play optimally.

Analysis

Key Observation

In this game, at any point in time, the remaining cards always form a contiguous subsequence (interval) of the original row. This is because players can only take from the left or right end, so cards are always removed from the ends.

For example, if \(A = [3, 1, -2, 5]\), when Takahashi takes \(3\) from the left end, the remaining cards are \([1, -2, 5]\), and when he takes \(5\) from the right end, the remaining cards are \([3, 1, -2]\) — both are contiguous intervals.

Problem with the Naive Approach

Exploring all possible choice patterns results in \(O(2^N)\) complexity since there are 2 choices at each turn and \(N\) turns in total, which causes TLE.

The Key: Interval DP

Since the remaining cards can always be represented as an interval \([l, r]\), the number of states is only \(O(N^2)\). The crucial idea is to define \(dp[l][r]\) as the maximum value of “my score − opponent’s score” from the perspective of the current player.

With this definition, the same recurrence can be used regardless of whether it is Takahashi’s or Aoki’s turn. The current player wants to maximize the score difference from their perspective:

\[dp[l][r] = \max(A[l] - dp[l+1][r],\; A[r] - dp[l][r-1])\]

• \(A[l] - dp[l+1][r]\): Take the left end and gain \(A[l]\). In the remaining interval \([l+1, r]\), the opponent takes their turn, and the score difference from the opponent’s perspective is \(dp[l+1][r]\), so from the current player’s perspective it becomes \(-dp[l+1][r]\).
• \(A[r] - dp[l][r-1]\): The case of taking the right end follows the same logic.

Algorithm

1. Initialize the DP table: For single-card intervals, \(dp[i][i] = A[i]\) (no choice but to take it).
2. Fill from shorter intervals to longer ones: In order of length \(2, 3, \ldots, N\), compute \(dp[l][r]\) for each interval \([l, r]\) using the recurrence above.
3. Recover the final result: \(dp[0][N-1]\) is “Takahashi’s score − Aoki’s score” from Takahashi’s perspective. Let the total sum be \(S = \sum A_i\), then:
   • Takahashi’s score \(+\) Aoki’s score \(= S\)
   • Takahashi’s score \(-\) Aoki’s score \(= dp[0][N-1]\)

Solving this system of equations: $\(\text{Takahashi's score} = \frac{S + dp[0][N-1]}{2}, \quad \text{Aoki's score} = \frac{S - dp[0][N-1]}{2}\)$

Complexity

• Time complexity: \(O(N^2)\) — there are \(O(N^2)\) intervals, and each transition takes \(O(1)\)
• Space complexity: \(O(N^2)\) — the size of the DP table

Implementation Notes

• The sign negation “\(-dp[l+1][r]\)” in the DP transition is crucial. When the turn changes, “self” and “opponent” swap, so the sign of the score difference is reversed.

• In interval DP, computation must proceed from shorter intervals to longer ones (length \(1 \to 2 \to \cdots \to N\)).

• Since all \(A_i\) are integers, \(S + dp[0][N-1]\) and \(S - dp[0][N-1]\) are always even, so integer division yields correct results (Takahashi and Aoki together take exactly \(N\) cards; if \(N\) is odd, the difference is also odd, but the sum and difference with \(S\) are always even).

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    # dp[l][r] = the value of (current player's score - opponent's score)
    # for the subarray A[l..r] when it's the current player's turn
    # Base case: dp[i][i] = A[i] (take the only card)
    
    # dp[l][r] = max(A[l] - dp[l+1][r], A[r] - dp[l][r-1])
    
    dp = [[0] * N for _ in range(N)]
    
    for i in range(N):
        dp[i][i] = A[i]
    
    for length in range(2, N + 1):
        for l in range(N - length + 1):
            r = l + length - 1
            take_left = A[l] - dp[l + 1][r]
            take_right = A[r] - dp[l][r - 1]
            dp[l][r] = max(take_left, take_right)
    
    # dp[0][N-1] = takahashi_score - aoki_score
    # takahashi_score + aoki_score = sum(A)
    total = sum(A)
    diff = dp[0][N - 1]
    
    takahashi = (total + diff) // 2
    aoki = (total - diff) // 2
    
    print(takahashi, aoki)

main()

---

This editorial was generated by claude4.6opus-thinking.