分数: 575 点
问题陈述
有 N 项目编号自 1 to N。 的 重量 项目的 项目数 i is W_i 和 值 is V_i.
你被给予 Q 查询,所以按顺序处理。 的 j第查询如下:
- 整数 给出了 L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) 。 从 items 中选择一些(可能是零)物品时 L_j,L_j+1,\dots,R_j 使得总重量不超过 C_j,找到所选项目的最大可能总价值。
约束
- 1\leq N \leq 2\times 10^4
- 1\leq Q \leq 2\times 10^5
- 1\leq W_i \leq 500
- 1\leq V_i \leq 10^9
- 1\leq L_j \leq R_j \leq N
- 1\leq C_j \leq 500
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N W_1 V_1 W_2 V_2 \vdots W_N V_N Q L_1 R_1 C_1 L_2 R_2 C_2 \vdots L_Q R_Q C_Q
输出
输出 Q 行。 的 i第行 (1\leq i \leq Q) 应包含以下问题的答案 i第一个查询。
示例输入 1
4 3 4 5 8 1 2 2 3 3 1 4 7 2 4 10 1 2 2
示例输出 1
11 13 0
对于第一个查询,在项目中 1,2,3,4,如果您选择项目 2,4,总重量为 5+2=7,不超过 C_1=7,总值为 8+3=11。这是最大值。
对于第二个查询,即使选择所有项目 2,3,4,总重量为 5+1+2=8,不超过 C_2=10,您可以获得的总价值为 8+2+3=13.
对于第三个查询,两项 1,2 重量超过 C_3=2,因此您不能选择任何项目,最大总值为 0.
示例输入 2
8 167 430302156 22 623690081 197 476190629 176 24979445 22 877914575 247 211047202 232 822804784 25 628894325 8 6 8 176 3 5 80 1 7 310 4 8 368 4 5 218 3 4 431 4 6 228 1 1 239
示例输出 2
628894325 877914575 2324409440 2329613684 902894020 501170074 902894020 430302156