CF859C Pie Rules

你可能听说过“派饼法则”（pie rule）：如果两个人想要公平地瓜分一块派饼，其中一个人切开，另一个人选取。现在 Alice 和 Bob 有很多块派饼，每一块都不用切分，完全由某一人吃掉。 他们决定谁吃哪一块派饼的方法如下：首先，确定所有派饼分发的顺序。Bob 初始持有一个特殊的“决策令牌”。在所有派饼分发完前，谁持有决策令牌，谁就将下一个派饼分给任一一方，并把决策令牌交给另一方。这一过程持续，直到没有派饼剩下。 所有派饼的质量都极佳，因此每个人都想让自己吃到的派饼总量最大。假设两人都选择最优策略，最终每个人各能吃到多少派饼？

输入的第一行为一个整数 $N$（$1 \leq N \leq 50$），表示派饼的块数。 接下来一行包含 $N$ 个整数，依次表示每一块派饼的大小（每个数字在 $1$ 到 $100000$ 之间），这些派饼的顺序在分发时不能改变。

输出两个整数。第一个表示 Alice 吃到的派饼总大小，第二个表示 Bob 吃到的派饼总大小。假设两人都以最优策略行事。

在第一个样例中，Bob 先将大小为 $141$ 的派饼给自己，并将决策令牌交给 Alice。随后，Alice 把大小为 $592$ 的派饼给 Bob，并让自己保留决策令牌，这样她就可以把剩下的大小为 $653$ 的派饼分给自己。 由 ChatGPT 5 翻译