P2975 [USACO10JAN] Taking Turns G

题目描述

有 $n$ 个格子，第 $i$ 个格子硬币数为 $W_i$ 。

牛A 和 牛B 轮流选某个格子（牛A先手），并获得该格子的硬币。

规定：每次选的格子编号递增。牛A第一次可以选 $1$ 到 $n$ 任意一个格子。

在保证自己能捡到最多的硬币的情况下，双方都希望对方能多捡硬币。

双方有采用最优策略，求问最后 它们 各捡到多少硬币。

输入格式：

第一行一个整数 $n(1\leq n\le 7\times 10 ^ 5)$，

下来有 $n$ 个整数 $W_i(1 \le W_i \le 2 \times 10 ^{9})$。

输出格式

一行两个整数，表示牛A和牛B硬币的最大值。

输入输出样例 #1

输入 #1

6 
17 
5 
9 
10 
3 
8

输出 #1

27 17