← 返回题目列表

AtCoder · abc426_g

G. 范围背包查询

中文机器翻译题面 查看原题

分数: 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