QOJ.ac

QOJ

Time Limit: 4 s Memory Limit: 6 MB Total points: 100
[+7]
统计

悲伤的故事

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

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

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

题目背景

Mayflower - Plum

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

题目描述

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

给定 n 个物品,体积依次为 v1,v2,,vn,价值依次为 w1,w2,,wn

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

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

  • 如果你可以先选定一个元素都在 (0,1] 之间的实数序列 p1,p2,,pn。并对于所有物品,第 i 个物品的体积和价值同时乘以 pi,即体积变为 pivi,价值变为 piwi。然后你再进行选择物品,那么你的收益最多为 r
  • 在原问题中,假设你的收益最多为 l,则有 rlk

输入格式

第一行三个正整数 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.inex_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

最终我们有 rl=379,又有 k=6,满足 rlk

数据范围

对于所有数据,保证 1n104,1m109,1k20,1vi5000,1wi1012

子任务编号 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 后,在满足 rlk 的所有的数据中等概率随机选一组。