← 返回题目列表

Codeforces · 859/C

C. 馅饼规则

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

您以前可能听说过馅饼规则。它规定,如果两个人希望公平地分享一块馅饼,一个人应该把馅饼切成两半,另一个人应该选择谁得到哪一块。爱丽丝和鲍勃有很多片馅饼,而不是把馅饼切成两半,而是每一片馅饼只会被一个人吃掉。

Alice 和 Bob 决定谁吃每一片的方式如下。首先,决定分发馅饼的顺序。有一种特殊的代币称为“决策者”代币,最初由鲍勃持有。在所有馅饼分发完毕之前,拥有决策者令牌的人将把下一块馅饼交给其中一个参与者,并将决策者令牌给另一个参与者。他们继续下去,直到没有留下任何馅饼。

所有切片的质量都非常好,因此每个参与者显然都希望最大化他们吃到的馅饼总量。假设两个参与者都做出了最佳决定,那么每个参与者将获得多少馅饼?

输入

输入将以整数 N (1 ≤ N ≤ 50) 开头,即饼图的切片数。

接下来是一行 N 个整数,指示切片的大小(每个整数在 1 到 100000 之间,包括 1 和 100000),按照它们必须分发的顺序排列。

输出

打印两个整数。首先是爱丽丝吃掉的切片大小的总和,然后是鲍勃吃掉的切片大小的总和,假设两个玩家都做出了最佳决定。

示例

输入 #1

3
141 592 653

输出 #1

653 733

输入 #2

5
10 21 10 21 10

输出 #2

31 41

注意

在第一个示例中,Bob 为自己获取大小为 141 的切片,并将决策者令牌交给 Alice。然后,Alice 将大小为 592 的切片交给 Bob,并为自己保留决策者令牌,以便她可以将大小为 653 的切片交给自己。