送礼物(Sending Gifts)
送礼物(Sending Gifts)
题目描述
作为惩罚，GY 被遣送去帮助某神牛给女生送礼物 (GY：貌似是个好差事）但是在 GY 看到礼物之后，他就不这么认为了。某神牛有 个礼物，且异常沉重，但是 GY 的力气也异常的大 (-_-b)，他一次可以搬动重量和在 以下的任意多个物品。GY 希望一次搬掉尽量重的一些物品，请你告诉他在他的力气范围内一次性能搬动的最大重量是多少。
输入格式
第一行两个整数，分别代表 和 。
以后 行，每行一个正整数表示 。
输出格式
仅一个整数，表示 GY 在他的力气范围内一次性能搬动的最大重量。
样例输入 #1
20 5
7
5
4
18
1
样例输出 #1
19
数据范围
对于所有测试数据，, 。
知识点与难度
本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。
测试点分布
| Subtask | 分值 | 测试点编号 | 说明 |
|---|---|---|---|
| 0 | 10 | 1 | 样例 |
| 1 | 20 | 2~8 | 小规模 N≤15 / 特殊: 全部物品总和≤W / 特殊: 单个物品恰好等于W |
| 2 | 15 | 9~11 | Hack: 所有物品均大于W输出0 / Hack: W=2^31-1防32位加法溢出 / Hack: N=46等权重复值 |
| 3 | 30 | 12~20 | 中规模 N≤34 / 大规模 N=46,W≤2^31-1 折半归并压力 |
| 4 | 25 | 21~25 | 随机 1≤N≤46,W,G_i≤2^31-1 回归 |
出处：原题链接