#CF381A. Sereja 和 Dima
Sereja 和 Dima
CF381A Sereja and Dima
题目描述
Sereja 和 Dima 玩一个游戏。游戏规则非常简单:他们有 张牌排成一行,每张牌上写着一个数字,所有牌上的数字互不相同。两名玩家轮流行动,Sereja 先手。在自己的回合中,玩家可以从当前牌堆的最左端或最右端取走一张牌。所有牌都被取光时,游戏结束。拥有手中牌面数字总和最大的玩家获胜。
Sereja 和 Dima 都非常贪心:每次轮到自己时,他们都会选择当前更大的那一张牌。
Inna 是 Sereja 和 Dima 的朋友。她知道两位玩家的策略,现在想预测最终的得分情况。请帮助她计算给定初始牌面状态下,最终的分数。
输入格式
第一行输入一个整数 代表牌的数量。
第二行输入 个整数 $a_1,a_2,\dots,a_n \left(1 \leqq a_i \leqq 1000\right)$ 代表从左到右每张牌上的数字。保证所有 互不相同。
输出格式
在一行上输出两个整数,分别代表游戏结束时 Sereja 和 Dima 的得分。
测试样例
4
4 1 2 10
12 5
样例 1 解释
Sereja 会取走数字为 和 的牌,得分为 ;Dima 会取走数字为 和 的牌,得分为 。
7
1 2 3 4 5 6 7
16 12