← 返回题目列表

AtCoder · agc026_f

F. 馒头游戏

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

分数: 2000 点

问题陈述

有 N 框从左到右排列成一排。的 i左边第一个框包含 a_i 馒头(豆沙馅的包子)。 杉木 和 西格玛 使用这些盒子玩游戏。 他们交替执行以下操作。 杉木 先走,当总共有 执行 N 操作。

  • 选择一个仍不包含棋子且与其他玩家在棋子中选择的盒子相邻的盒子。 最后 操作,然后将一块放入该盒子中。如果有多个这样的框,则可以选择其中任何一个。
  • 如果没有满足上述条件的盒子,或者这是 杉木的第一个操作,选择任意一个还没有包含棋子的盒子,然后将棋子放入该盒子中。

游戏结束时,每个玩家都可以将馒头放入他放置棋子的盒子中。 他们热爱馒头,并且每个人都有足够的智慧来执行最佳动作,以便在游戏结束时获得最大数量的馒头。

求游戏结束时每个玩家将拥有的馒头数量。

约束

  • 2 \leq N \leq 300 000
  • 1 \leq a_i \leq 1000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 ... a_N

输出

打印以下数字 杉木的馒头和 西格玛游戏结束时的馒头,按此顺序排列,中间有一个空格。


示例输入 1

5
20 100 10 1 10

示例输出 1

120 21

如果两人执行了最佳动作,则游戏进行如下:

  • 首先, 杉木 必须把他的棋子放在左边第二个盒子里。
  • 然后, 西格玛 必须把他的棋子放在最左边的盒子里。
  • 然后, 杉木 把他的棋子放在第三个或第五个盒子里。
  • 然后, 西格玛 将他的棋子放入第四个盒子中。
  • 最后, 杉木 将他的棋子放入剩余的盒子中。

示例输入 2

6
4 5 1 1 4 5

示例输出 2

11 9

示例输入 3

5
1 10 100 10 1

示例输出 3

102 20
{示例示例_3} 答案可能无法表示为 <var>32</var> 位整数。