悲伤的故事
由于现场出现了预料之外的做法。
因此现在是经过修改后的范围和数据,集训队互测现场的情况并没有参考价值。
如果你觉得你的做法空间正确且获得了 MLE,请尝试替换引用的头文件。
题目背景
五月和七月收拾好自己的东西,分别踏上了属于自己的路……
题目描述
请注意本题不常规的空间限制。
给定 n 个物品,体积依次为 v1,v2,…,vn,价值依次为 w1,w2,…,wn。
你需要从中选择一些物品,保证体积和不超过 m。你将会带走你选择的物品,你的收益是这些物品的价值和。输出你的收益的最大值。
特别地,有一个每次给定的系数 k,数据保证如下性质:
- 如果你可以先选定一个元素都在 (0,1] 之间的实数序列 p1,p2,…,pn。并对于所有物品,第 i 个物品的体积和价值同时乘以 pi,即体积变为 pivi,价值变为 piwi。然后你再进行选择物品,那么你的收益最多为 r。
- 在原问题中,假设你的收益最多为 l,则有 r−l≤k。
输入格式
第一行三个正整数 n,m,k。
接下来 n 行,第 i 行两个正整数 vi,wi。
输出格式
一行一个数,表示答案。
样例 0
样例 0 输入
8 20 6
10 6
9 8
6 3
2 5
6 8
3 8
1 9
4 2
样例 0 输出
33
附加样例 1~7
见附件下载中的 ex_mayflower1~7.in
与 ex_mayflower1~7.out
。
附加样例依次满足本题的 7 个子任务的限制。
样例解释
在题面中给定的样例中,r 可以通过如下方式计算:
- 令 p=[1,89,1,1,1,1,1,1],即对于第 2 个物品,将其体积变为 8,价值变为 649,其他物品不变。然后选取第 2,4,5,6,7 这五个物品。此时总体积为 8+2+6+3+1=20,总价值为 r=649+5+8+8+9=3349。可以证明找不出更大的 r。
而 l 可以通过如下方式计算:
- 选取第 2,5,6,7 这四个物品。此时总体积为 9+6+3+1=19,总价值为 l=8+8+8+9=33。可以证明找不出更大的 l。
最终我们有 r−l=379,又有 k=6,满足 r−l≤k。
数据范围
对于所有数据,保证 1≤n≤104,1≤m≤109,1≤k≤20,1≤vi≤5000,1≤wi≤1012。
子任务编号 | n≤ | m≤ | k≤ | vi≤ | wi≤ | 数据随机 | 分值 |
---|---|---|---|---|---|---|---|
1 | 1000 | 105 | 20 | 1000 | 1012 | 否 | 5 |
2 | 1000 | 109 | 20 | 1000 | 1012 | 否 | 5 |
3 | 104 | 109 | 20 | 333 | 333 | 否 | 10 |
4 | 104 | 109 | 1 | 2000 | 1012 | 否 | 20 |
5 | 104 | 109 | 5 | 2000 | 2000 | 是 | 15 |
6 | 104 | 109 | 20 | 2000 | 2000 | 是 | 15 |
7 | 104 | 109 | 20 | 5000 | 1012 | 否 | 30 |
数据随机:对于每组数据,给定 n,m,k 后,在满足 r−l≤k 的所有的数据中等概率随机选一组。