第 4 题 大柿子 (bigpersimmon)

CSP-S 复赛模拟赛 23 · 时间限制 2 s · 空间限制 1024 MB · 54 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 bigpersimmon.in，输出文件 bigpersimmon.out。

题目描述

Alice 和 Bob 买了一个大柿子，把它切成 $n$ 块，大小分别为 $w_1, \ldots, w_n$，随即开始吃。两个孩子会同时进食，对每个人来说，进食过程如下：

一旦有人吃完自己手上的这一块（以及在进食刚开始时），他就会挑选下一块并开始吃。若取了一块大小为 $w$ 的柿子，吃它恰好需要 $w$ 秒，然后就要挑选新的一块。若两人同时吃完手上的这一块（或者进食刚刚开始），则由 Alice 先挑选一块，但他们会同时开始吃。挑选新的一块不花费时间。

由于 Alice 和 Bob 都是完美主义者，他们挑选时只会从剩余的所有块中取最小的（$w_i$ 最小的）或最大的（$w_i$ 最大的）那一块。

当最后一个人吃完，且没有剩余的块时，进食过程结束。

Alice 和 Bob 都希望尽可能多吃。若两人都最优地挑选块，求 Alice 吃掉的柿子总大小与 Bob 吃掉的柿子总大小。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2000$）——柿子块数。

第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \le w_i \le 20\,000$，$w_i \le w_{i+1}$）——各块柿子的大小。

记 $W$ 为所有块的大小之和。保证 $W \le 20\,000$。

输出格式

在一行中输出两个数——若两人都最优地挑选块，Alice 吃掉的柿子总大小与 Bob 吃掉的柿子总大小。

样例

样例 1

输入：

5
1 1 3 4 6

输出：

8 7

样例 2

输入：

4
1 1 2 2

输出：

3 3

样例 3

输入：

4
1 7 7 9

输出：

10 14

样例解释

在第一个样例中，Alice 应先取一块大小为 1 的。紧接着 Bob 也应取一块大小为 1 的。一秒后，Alice 会取一块大小为 3 的，然后 Bob 会取一块大小为 6 的。3 秒后，Alice 会取一块大小为 4 的。3 秒后，Bob 吃完，再过一秒整个过程结束。此时 Alice 吃了大小为 $1 + 3 + 4 = 8$ 的块，Bob 吃了 $1 + 6 = 7$。

在第三个样例中，Alice 应取一块大小为 1 的，Bob 应取一块大小为 7 的。一秒后，Alice 会取一块大小为 9 的，6 秒后，Bob 会取一块大小为 7 的。

约束与子任务

本题的测试点分为四个组。只有当该组的所有测试点以及所有所需的组都通过时，该组的分数才会被计入。请注意，有些组不要求通过样例测试。离线评测（Offline-evaluation） 指你的程序在该组上的测试结果要比赛结束后才可知。