D. 区间背包

    传统题 3000ms 256MiB

区间背包

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

大样例下载

题目描述

有 nn 个物品,编号为 11 至 nn。

第 ii 个物品的体积为 wiw_i,价值为 viv_i。

有 qq 次询问,每次询问形如 Li,Ri,WiL_i,R_i,W_i。

对于每次询问,你需要回答以下问题

从编号 LiL_i 到 RiR_i 的物品中选择若干物品放进容量为 WiW_i 的背包里,每个物品最多只能放一次。能装的价值最大是多少?

输入格式

第一行两个整数 n,qn,q 。

第二行 nn 个整数,表示 ww。

第三行 nn 个整数,表示 vv。

接下来 qq 行,每行三个整数 Li,Ri,WiL_i,R_i,W_i,表示一次询问。

输出格式

每个询问输出一个整数,表示答案。

每个数占一行。

样例

input

5 3
1 2 3 4 5
1 2 3 4 5
1 2 3
2 4 4
2 4 8

output

3
4
7

样例解释

询问 1: 可以选取第一个,第二个物品,所占体积为 33,价值为 33。

询问 2: 可以选取第四个物品,所占体积为 44,价值为 44。

询问 3: 可以选取第三个,第四个物品,所占体积为 77,价值为 77。背包不必放满。但是不能放 44 个第二个物品,因为 一次询问中,每个物品只能拿一次。但不同的询问之间互不干扰,比如询问 2 和询问 3 都可以拿第四个物品。

可以证明,这是最优方法。

数据范围

对于前 20%20\% 的数据,1≤n,q≤100,1≤Wi,wi,vi≤501 \le n,q \le 100, 1 \le W_i ,w_i,v_i \le 50。

对于前 50%50\% 的数据,1≤n,q≤105,1≤Wi,wi,vi≤501 \le n,q \le 10^5, 1 \le W_i ,w_i,v_i \le 50。

对于 100%100\% 的数据,$1 \le n,q \le 5 \times 10^5, 1 \le W_i ,w_i,v_i \le 50,1 \le L_i,R_i \le n ,\sum _{i=1} ^{n-1} (\mid L_{i+1} -L_i \mid + \mid R_{i+1} -R_i \mid) \le 10^6$。

2026-07-10

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-7-10 7:30
结束于
2026-7-10 11:00
持续时间
3.5 小时
主持人
参赛人数
31