分道扬镳 - 题目

由于现场出现了预料之外的做法。

因此现在是经过修改后的范围和数据，集训队互测现场的情况并没有参考价值。

如果你觉得你的做法空间正确且获得了 MLE，请尝试替换引用的头文件。

五月和七月收拾好自己的东西，分别踏上了属于自己的路……

请注意本题不常规的空间限制。

给定 $n$ 个物品，体积依次为 $v_1, v_2, \dots, v_n$，价值依次为 $w_1, w_2, \dots, w_n$。

你需要从中选择一些物品，保证体积和不超过 $m$。你将会带走你选择的物品，你的收益是这些物品的价值和。输出你的收益的最大值。

特别地，有一个每次给定的系数 $k$，数据保证如下性质：

如果你可以先选定一个元素都在 $(0, 1]$ 之间的实数序列 $p_1, p_2, \dots, p_n$。并对于所有物品，第 $i$ 个物品的体积和价值同时乘以 $p_i$，即体积变为 $p_iv_i$，价值变为 $p_iw_i$。然后你再进行选择物品，那么你的收益最多为 $r$。
在原问题中，假设你的收益最多为 $l$，则有 $r-l\leq k$。

第一行三个正整数 $n, m, k$。

接下来 $n$ 行，第 $i$ 行两个正整数 $v_i, w_i$。

一行一个数，表示答案。

见附件下载中的 ex_mayflower1~7.in 与 ex_mayflower1~7.out。

附加样例依次满足本题的 $7$ 个子任务的限制。

在题面中给定的样例中，$r$ 可以通过如下方式计算：

令 $p = [1, \frac 8 9, 1, 1, 1, 1, 1, 1]$，即对于第 $2$ 个物品，将其体积变为 $8$，价值变为 $\frac {64} 9$，其他物品不变。然后选取第 $2, 4, 5, 6, 7$ 这五个物品。此时总体积为 $8+2+6+3+1=20$，总价值为 $r = \frac {64} 9 + 5 + 8 + 8 + 9 = \frac {334} 9$。可以证明找不出更大的 $r$。

而 $l$ 可以通过如下方式计算：

选取第 $2, 5, 6, 7$ 这四个物品。此时总体积为 $9+6+3+1=19$，总价值为 $l = 8 + 8 + 8 + 9 = 33$。可以证明找不出更大的 $l$。

最终我们有 $r - l = \frac {37} 9$，又有 $k = 6$，满足 $r - l \leq k$。

对于所有数据，保证 $1 \leq n \leq 10^4, 1 \leq m \leq 10^9, 1 \leq k \leq 20, 1 \leq v_i \leq 5000, 1 \leq w_i \leq 10^{12}$。

子任务编号	$n \leq$	$m \leq$	$k \leq$	$v_i \leq$	$w_i \leq$	数据随机	分值
1	$1000$	$10^5$	$20$	$1000$	$10^{12}$	否	5
2	$1000$	$10^9$	$20$	$1000$	$10^{12}$	否	5
3	$10^4$	$10^9$	$20$	$333$	$333$	否	10
4	$10^4$	$10^9$	$1$	$2000$	$10^{12}$	否	20
5	$10^4$	$10^9$	$5$	$2000$	$2000$	是	15
6	$10^4$	$10^9$	$20$	$2000$	$2000$	是	15
7	$10^4$	$10^9$	$20$	$5000$	$10^{12}$	否	30

数据随机：对于每组数据，给定 $n, m, k$ 后，在满足 $r - l \leq k$ 的所有的数据中等概率随机选一组。

QOJ.ac