P3004 [USACO10DEC] Treasure Chest S

Bessie and Bonnie have found a treasure chest full of marvelous gold coins! Being cows, though, they can't just walk into a store and buy stuff, so instead they decide to have some fun with the coins. The N (1

- The first line contains an integer $n$, the number of coins. - Lines $2$ to $(n + 1)$ each contain one integer. The integer on line $(i + 1)$ is the value $c_i$ of the $i$-th coin.

Output a single integer: the maximum total value that player A can obtain.

- Sample explanation: Initially, the coin sequence is $\{30,~25,~10,~35\}$. - Turn 1: A takes the rightmost coin, the sequence becomes $\{30,~25,~10\}$, and A’s total is $35$. - Turn 2: B takes the leftmost coin, the sequence becomes $\{25,~10\}$, and B’s total is $30$. - Turn 3: A takes the leftmost coin, the sequence becomes $\{10\}$, and A’s total is $35 + 25 = 60$. - Turn 4: B takes the leftmost coin, the sequence becomes empty, and B’s total is $30 + 10 = 40$. The game ends. The maximum total value that A can obtain is $60$. - Constraints: For all testdata, $1 \leq n \leq 5 \times 10^3$, $1 \leq c_i \leq 5 \times 10^3$. - Note: The memory limit is $64$ MiB. Translated by ChatGPT 5