← 返回题目列表

AtCoder · awc0054_d

D. 拿牌游戏

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥和青木玩纸牌游戏。

有 N 卡片在桌子上排成一排。的 i左起第张牌有一个整数 上面写着 A_i (A_i 可以为负)。

游戏规则如下:

  1. 高桥先行,高桥和青木轮流轮流。
  2. 在轮到他们时,玩家必须准确选择 从当前行的左端或右端选择 1 卡并将其添加到他们的手牌中。所选的牌将从该行中移除,其余的牌保持其在该行中的顺序。
  3. 当所有牌都被拿走后,游戏结束。

每个玩家的 分数 是他们收集的卡片上写的整数的总和。两名玩家都以最佳方式发挥最大(他们自己的分数) - (对手的得分)。

当两名玩家都发挥最佳状态时,分别求高桥的得分和青木的得分。

约束

  • 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