TopCoder

weyryafjnm;

erfvjuaweikm

User's AC Ratio

89.7% (200/223)

Submission's AC Ratio

53.6% (288/537)

Description

「A遊戲」是個由兩個人玩的遊戲：有一串由 $N$ 個正整數所組成的數列，兩個玩者輪流拿走一個最左邊或最右邊的數，直到最後所有的數都取完之後，兩個玩者分別把自己所取到數加總，分數較高的人獲勝。
　　今假設兩個玩者都是最佳玩家──也就是說，兩者都不會犯錯，會就目前狀況盡自己的力取得盡量多的分數──試求兩個玩家所能得到的最高分數各為多少？

Input Format

首先是一個正整數 $N$，代表有幾個數（$1 \leq N \leq 1000$）。接下來有 $N$ 個正整數，代表遊戲開始時的這列數。

Output Format

兩個數字：第一位玩家（先拿者）的分數，以及第二位玩家的分數。

Sample Input

6
4 7 2 9 5 2

Sample Output

18 11

Hints

Problem Source

原TIOJ1029 / 96建中校內資訊能力競賽(prob6)
2021.03.01 Update: Added $\LaTeX$ by FHVirus

Subtasks

No.	Testdata Range	Score
1	0	12
2	1	12
3	2	12
4	3	12
5	4	12
6	5	12
7	6	12
8	7	16

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	600	262144	262144	1
1	600	262144	262144	2
2	600	262144	262144	3
3	600	262144	262144	4
4	600	262144	262144	5
5	600	262144	262144	6
6	600	262144	262144	7
7	600	262144	262144	8

Submit

Status

Ranklist

1029 . A遊戲