比赛场次 391
比赛名称 叫图论的DP题
比赛状态 已结束比赛成绩
开始时间 2017-08-29 19:00:00
结束时间 2017-08-30 22:00:00
开放分组 全部用户
组织者 Hyoi_ctime
注释介绍
题目名称 待售干草
输入输出 hay4sale.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 11 简单对比
用户 结果 时间 内存 得分
Gravatar@@@ AAAAAAAAAAA 0.002 s 0.50 MiB 100
GravatarkZime AAAAAAAAAAA 0.003 s 0.29 MiB 100
GravatarRegnig Etalsnart AAAAAAAAAAA 0.281 s 0.07 MiB 100
Gravatar东林桂香 AAAAAAAAAAA 0.313 s 0.52 MiB 100
Gravatarbear AAAAAAAAAAA 0.333 s 0.52 MiB 100
GravatarFFF团 AAAAAAAAAAA 0.978 s 0.74 MiB 100

6. 待售干草

★   输入文件:hay4sale.in   输出文件:hay4sale.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

约翰经历了一个可怕的损失,庞大的澳大利亚蟑螂吃掉了他所有的干草存货,以至于他没有任何食物喂奶牛了。

在奶牛饥饿前,他拉起他容量为 $C (1 \leq C \leq 50,000)$ 的货车找农场主堂君要一些干草。

堂有多种多样的干草包共 $H (1 \leq H \leq 5,000)$ 捆,每捆都有一个体积 $(1 \leq V_i \leq C)$。

众所周知,干草是软的,能被挤进货车中。

约翰在计算如何购买最多的干草。

给出可以买的每捆干草的容量,但不能买每捆的一部分。

【输入格式】

第一行:两个用空格隔开的整数:$C$ 和 $H$;

第 $2 \sim H+1$ 行:每行是一个干草捆的容量值:$V_i$。

【输出格式】

只有一行,一个单独的整数,约翰能购买的最大干草总体积。

【输入样例】

7 3
2
6
5

【输出样例】

7

【输入输出样例解释】

货车容量为 $7$;$3$ 捆要出售的干草值分别为 $2,6,5$。

所以购买两捆小的干草捆 $2,5$。