#PQJ1816x9517. QOJ 1816_9517
QOJ 1816_9517
标题: 分道扬镳 - Problem - QOJ.ac
#9517. 分道扬镳
The problem was used in the following contests:
悲伤的故事
由于现场出现了预料之外的做法。
因此现在是经过修改后的范围和数据,集训队互测现场的情况并没有参考价值。
如果你觉得你的做法空间正确且获得了 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 的所有的数据中等概率随机选一组。