分数: 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
- 第一行包含一个整数 N,代表卡片数量。
- 第二行包含整数 每张卡片上写有 A_1, A_2, \ldots, A_N ,并用空格分隔。
输出
按顺序打印 Takahashi 的分数和 Aoki 的分数,并用空格分隔在一行上。
示例输入 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