#CF381A. Sereja 和 Dima

Sereja 和 Dima

CF381A Sereja and Dima

题目描述

\hspace{15pt}Sereja 和 Dima 玩一个游戏。游戏规则非常简单:他们有 nn 张牌排成一行,每张牌上写着一个数字,所有牌上的数字互不相同。两名玩家轮流行动,Sereja 先手。在自己的回合中,玩家可以从当前牌堆的最左端或最右端取走一张牌。所有牌都被取光时,游戏结束。拥有手中牌面数字总和最大的玩家获胜。

\hspace{15pt}Sereja 和 Dima 都非常贪心:每次轮到自己时,他们都会选择当前更大的那一张牌。

\hspace{15pt}Inna 是 Sereja 和 Dima 的朋友。她知道两位玩家的策略,现在想预测最终的得分情况。请帮助她计算给定初始牌面状态下,最终的分数。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦1000)n \left(1 \leqq n \leqq 1000\right) 代表牌的数量。

\hspace{15pt}第二行输入 nn 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 1000\right)$ 代表从左到右每张牌上的数字。保证所有 aia_i 互不相同。

输出格式

\hspace{15pt}在一行上输出两个整数,分别代表游戏结束时 Sereja 和 Dima 的得分。

测试样例

4
4 1 2 10

12 5

样例 1 解释

\hspace{15pt}Sereja 会取走数字为 1010 和 22 的牌,得分为 1212;Dima 会取走数字为 44 和 11 的牌,得分为 55。

7
1 2 3 4 5 6 7

16 12