

Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 575 点
問題文
1 から N までの番号が付けられた N 個のアイテムがあります。 アイテム i の 重み は W_i、価値 は V_i です。
Q 個のクエリが与えられるので、順に処理してください。 j 番目のクエリは以下の通りです。
- 整数 L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) が与えられる。 アイテム L_j,L_j+1,\dots,R_j のうちいくつか(0 個でもよい)を、重みの総和が 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 番目のクエリについて、アイテム 1,2,3,4 のうちアイテム 2,4 を選ぶと、重みの総和は 5+2=7 となり C_1=7 を超えず、価値の総和として 8+3=11 を達成できます。これが最大です。
2 番目のクエリについて、アイテム 2,3,4 全てを選んでも、重みの総和は 5+1+2=8 となり C_2=10 を超えず、価値の総和として 8+2+3=13 を達成できます。
3 番目のクエリについて、アイテム 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
Score : 575 points
Problem Statement
There are N items numbered from 1 to N. The weight of item i is W_i and the value is V_i.
You are given Q queries, so process them in order. The j-th query is as follows:
- Integers L_j, R_j, C_j\ (1\leq L_j\leq R_j\leq N) are given. When choosing some (possibly zero) items from items L_j,L_j+1,\dots,R_j such that the total weight does not exceed C_j, find the maximum possible total value of the chosen items.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
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
Output
Output Q lines. The i-th line (1\leq i \leq Q) should contain the answer for the i-th query.
Sample Input 1
4 3 4 5 8 1 2 2 3 3 1 4 7 2 4 10 1 2 2
Sample Output 1
11 13 0
For the first query, among items 1,2,3,4, if you choose items 2,4, the total weight is 5+2=7, which does not exceed C_1=7, and the total value is 8+3=11. This is the maximum.
For the second query, even if you choose all items 2,3,4, the total weight is 5+1+2=8, which does not exceed C_2=10, and you can achieve a total value of 8+2+3=13.
For the third query, both items 1,2 have weights exceeding C_3=2, so you cannot choose any item, and the maximum total value is 0.
Sample Input 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
Sample Output 2
628894325 877914575 2324409440 2329613684 902894020 501170074 902894020 430302156