配点: 100 点
英雄比特太郎即将承担保护村庄免受怪物侵害的防御任务。 防御战的难度等级为 1 以上 L 用以下整数表示,该值可以在挑战时选择。 难度级别 \ell (1 \leqq \ell \leqq L) 防御战中,出现的怪物的HP为(难度 (基于 1 的案例) \ell 将增加一倍。
防御战是 它发生 T 秒,N 身体怪兽陆续出现。 给怪物 它们的编号最大为 1 假设一直下雨,直到 N 。 防御战开始后 t 秒後 (0 \leqq t \leqq T) 是时间 它被称为 t 。 怪物 i (1 \leqq i \leqq N) 是时间 S_i (0 \leqq S_i < T) 出现在 它的强度是 P_i ,其生命值取决于防御战的难度。 作为 \ell ,\ell \times H_i 。
在防御战中,Bitaro可以多次执行以下操作。
- 当前出现的怪物中 1 选择主体,1 在几秒内攻击该怪物。该怪物的HP为 1 减少。惠普是 变成 0 的怪物倒塌并且不能再攻击。
時刻 T ,防御战结束,防御战结束。 評価値 计算如下。
- 時刻 T 之后的怪物 i (1 \leqq i \leqq N) 的生命值 h_i ,评价值为 h_1 P_1 + h_2 P_2 + \dots + h_N P_N 。
评价值是任务确定的标准值。 m Bitaro 可以完成任务当且仅当:
完成任务的难度越高,奖励就越大,所以Bitaro想要找到他可以完成任务的最大难度。 然而,由于事先不知道标准值,BitaroQ 候选参考值 关于 M_1, M_2, \dots, M_Q , 我决定找到能够让我完成任务的最大难度级别。
当给出防御战信息和标准值候选信息时,确定是否可以完成每个标准值候选的任务, 如果可能的话,编写一个程序来找出可以完成任务的最大难度级别。 输出
入力
输入是按以下格式从标准输入给出的。
N L T S_1 H_1 P_1 S_2 H_2 P_2 \vdots S_N H_N P_N Q M_1 M_2 \vdots M_Q
出力
Q 行。
j 行目 (1 \leqq j \leqq Q)有m = M_j 输出可以完成任务的最大难度。如果您无法完成任何难度的任务,请改为
在 0 。
如果有多个答案与
制約
- 1 \leqq N \leqq 6\,000.
- 1 \leqq L \leqq 10\,000\,000.
- 1 \leqq T \leqq 10^{18}.
- 0 \leqq S_i < T (1 \leqq i \leqq N).
- 1 \leqq H_i (1 \leqq i \leqq N).
- 1 \leqq P_i (1 \leqq i \leqq N).
- H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leqq 10^{11}.
- 1 \leqq Q \leqq 1\,000\,000.
- 0 \leqq M_j \leqq 10^{18} (1 \leqq j \leqq Q).
- M_1 < M_2 < \cdots < M_Q.
- 所有输入值都是整数。 第
小課題
- (1 点) N \leqq 30,Q = 1,M_1 = 0,L = 1.
- (3 点) N \leqq 30,Q = 1,M_1 = 0.
- (10 点) N \leqq 30,Q \leqq 3.
- (10 点) Q \leqq 3.
- (35 点) N \leqq 30.
- (8 点) N \leqq 400.
- (20 点) N \leqq 1\,800.
- (13 点)没有额外的限制。
入力例 1
2 2 10 0 9 2 8 5 1 3 0 20 40
出力例 1
0 1 2
難易度 1 的防御战中,你可以通过以下行动来增加你的评价值。 4 可以实现。评价值 3 无法实现以下目标。
| 時刻 | 出来事 |
|---|---|
| 0 | 怪物 1 (惠普 9) 出现。 攻击 |
| 0 – 8 | 怪物 1 向 8 次。怪物 1 的生命值为 它减少到 9 假设一直下雨,直到 1 。 |
| 8 | 怪物 2 (惠普 5) 出现。 攻击 |
| 8 – 9 | 怪物 2 向 1 次。怪物 2 的生命值为 它减少到 5 假设一直下雨,直到 4 。 |
| 9 – 10 | 怪物 1 向 1 次。怪物 1 的生命值为 它减少到 1 假设一直下雨,直到 0 。 |
| 10 | 怪物 1 崩溃了。 |
| 10 | 防御战结束。评价值为 0 \times P_1 + 4 \times P_2 = 4 变为。 |
另外,难度级别 2 的防御战中,你可以通过以下行动来增加你的评价值。 26 可以实现。评价值 25 无法实现以下目标。
| 時刻 | 出来事 |
|---|---|
| 0 | 怪物 1 (惠普 18) 出现。 攻击 |
| 0 – 8 | 怪物 1 向 8 次。怪物 1 的生命值为 它减少到 18 假设一直下雨,直到 10 。 |
| 8 | 怪物 2 (惠普 10) 出现。 攻击 |
| 8 – 10 | 怪物 1 向 2 次。怪物 1 的生命值为 它减少到 10 假设一直下雨,直到 8 。 |
| 10 | 防御战结束。评价值为 8 \times P_1 + 10 \times P_2 = 26 变为。 |
此外,在此输入示例中, L = 2 ,所以难度级别是 3 无法选择防御战。因此,输出如下。
- 1 第参考值 M_1 = 0 无法完成任何难度级别的任务,所以1 在线
来自
0。 在 - 2 第参考值 M_2 = 20 最大难度为 你可以完成 1 保卫战为止的任务, 给出了2 在线 来自 1 。 在
- 3 第参考值 M_3 = 40 最大难度为 你可以完成 2 保卫战为止的任务, 给出了3 在线 来自 2 。 在
此输入示例是一个小作业。 3, 4, 5, 6, 7, 8 满足约束。
入力例 2
3 1 100000000000 60000000000 30000000000 1 30000000000 45000000000 1 10000000000 10000000000 1 1 0
出力例 2
0
此输入示例满足所有子任务约束。
入力例 3
3 10000000 100000000 60000000 4 1 30000000 6 1 0 2 1 1 0
出力例 3
7000000
此输入示例是一个小作业。 2, 3, 4, 5, 6, 7, 8 满足约束。
入力例 4
5 20 100 0 3 1 20 2 2 40 1 3 60 4 4 80 2 5 11 0 50 100 150 200 250 300 350 400 450 500
出力例 4
6 8 10 12 13 15 16 18 19 20 20
此输入示例是一个小作业。 5, 6, 7, 8 满足约束。
入力例 5
15 10000000 1000000000000 160278118759 43084 33592 442653603914 19490 23090 824219815410 50858 89563 502303340628 56629 45080 495062829942 87342 28821 234536700105 45384 34328 396080693809 78081 50812 734374391045 40873 92012 122606844331 25451 30426 204076581972 58431 13989 495156368673 54276 41670 812963939390 27614 50228 405067019838 96324 18477 464546304875 67562 45956 528559327980 41759 15546 10 216000000000000 1728000000000000 5832000000000000 13824000000000000 27000000000000000 46656000000000000 74088000000000000 110592000000000000 157464000000000000 216000000000000000
出力例 5
995176 1135557 1431775 1824183 2359362 3059523 3942014 5106209 6594716 8448125
此输入示例是一个小作业。 5, 6, 7, 8 满足约束。