OpenJudge

1041:2013-10-05 很重的书

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
256000kB
描述

A 和B 将组队参加下周的ICPC 。比赛的组织者允许参赛者从当地的图书馆内借书。其中,
第i 本书的重量为w [i ]克。A 和B 想带上尽可能多的书,但每人都抱怨自己负担的书太重。
用T 表示A 带的书的总重量,W 为B 带的书的总重量。A 想最大化W-T ,而B 想最大化
T-W 。如果有多种选择,他们都愿意最大化T+W 。两人选择书的方式如下:
�首先,A 从图书馆借n [0 ]本书,放进B 的背包内;
�然后,B 从自己背包内取出n [1 ]本书,放进A 的背包内;
�接下来,A 又从自己的背包内取出n [2 ]本书,放进B 的背包内,
�依次类推……
整个过程进行m 次。如果过程中n [i ]比背包内书的总数目还多,那么就移走所有书到另一个人的背包内。
你的任务是求出最后两人背包中书的重量。

输入
第一行为s,m ,表示图书馆书的数目及选书的过程数(n 数组的大小)。第二
行是s 本书的重量。第三行为n [0 ],n [1 ],...,n [m-1 ]。
输出
两个数,分别为T,W 。
样例输入
4 5
5 2 3 1
3 2 1 1 1
**********
3 2
10 100 1000
2 3
样例输出
3 7
**********
110 0
提示
数据规模:
对于50%的数据,s<=20 ,m<=20 ;
对于100%的数据,s,m<=50 ,书的重量大于等于1 ,且不超过10 ^6 ,对所有0<=i1<=n [i ]<=s 。

crf is sb
crf is er gou dan
crf is sha diao

全局题号
6354
添加于
2013-10-05
提交次数
1
尝试人数
1
通过人数
1