/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君と青木君がカードを使ったゲームをします。
テーブルの上に N 枚のカードが一列に並べられています。左から i 番目のカードには整数 A_i が書かれています（A_i は負の値をとることもあります）。
ゲームのルールは以下の通りです：
- 高橋君が先手となり、高橋君と青木君が交互に手番を行う。
- 自分の手番では、現在の列の左端または右端のカードをちょうど 1 枚選んで取り、自分の手元に加えなければならない。取られたカードは列から除かれ、残りのカードはそのままの順序で列を成す。
- すべてのカードが取られたらゲーム終了となる。
各プレイヤーの 得点 は、そのプレイヤーが手元に集めたカードに書かれた整数の合計とします。両者はともに（自分の得点）-（相手の得点）を最大化するように最適に行動します。
両者が最適に行動したとき、高橋君の得点と青木君の得点をそれぞれ求めてください。
制約
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
N A_1 A_2 \ldots A_N
- 1 行目には、カードの枚数を表す整数 N が与えられる。
- 2 行目には、各カードに書かれた整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
高橋君の得点と青木君の得点を、この順にスペース区切りで 1 行に出力せよ。
入力例 1
4 1 2 3 4
出力例 1
6 4
入力例 2
5 3 -1 2 -5 4
出力例 2
-2 5
入力例 3
8 10 -3 7 2 -8 5 1 6
出力例 3
14 6
入力例 4
20 15 -7 23 -4 8 19 -12 6 3 -1 14 -9 7 25 -3 11 2 -18 20 5
出力例 4
77 27
入力例 5
1 -1000000000
出力例 5
-1000000000 0
Score : 400 pts
Problem Statement
Takahashi and Aoki play a game using cards.
There are N cards arranged in a row on the table. The i-th card from the left has an integer A_i written on it (A_i can be negative).
The rules of the game are as follows:
- Takahashi goes first, and Takahashi and Aoki take turns alternately.
- On their turn, a player must choose exactly 1 card from either the left end or the right end of the current row and add it to their hand. The chosen card is removed from the row, and the remaining cards maintain their order in the row.
- The game ends when all cards have been taken.
Each player's score is the sum of the integers written on the cards they have collected. Both players play optimally to maximize (their own score) - (the opponent's score).
When both players play optimally, find Takahashi's score and Aoki's score, respectively.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N, representing the number of cards.
- The second line contains the integers A_1, A_2, \ldots, A_N written on each card, separated by spaces.
Output
Print Takahashi's score and Aoki's score, in this order, separated by a space, on a single line.
Sample Input 1
4 1 2 3 4
Sample Output 1
6 4
Sample Input 2
5 3 -1 2 -5 4
Sample Output 2
-2 5
Sample Input 3
8 10 -3 7 2 -8 5 1 6
Sample Output 3
14 6
Sample Input 4
20 15 -7 23 -4 8 19 -12 6 3 -1 14 -9 7 25 -3 11 2 -18 20 5
Sample Output 4
77 27
Sample Input 5
1 -1000000000
Sample Output 5
-1000000000 0