#PQJ1816x9517. QOJ 1816_9517

    ID: 2714 传统题 4000ms 6MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2024-2025 集训队互测动态规划

QOJ 1816_9517

标题: 分道扬镳 - Problem - QOJ.ac

#9517. 分道扬镳

Statistics

The problem was used in the following contests:

悲伤的故事

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

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

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

题目背景

Mayflower - Plum

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

题目描述

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

给定 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 的所有的数据中等概率随机选一组。