← 返回题目列表

AtCoder · joisp2025_g

G. 勇敢的比特太郎 3(勇敢的比特太郎 3)

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

配点: 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. (1 点) N \leqq 30,Q = 1,M_1 = 0,L = 1.
  2. (3 点) N \leqq 30,Q = 1,M_1 = 0.
  3. (10 点) N \leqq 30,Q \leqq 3.
  4. (10 点) Q \leqq 3.
  5. (35 点) N \leqq 30.
  6. (8 点) N \leqq 400.
  7. (20 点) N \leqq 1\,800.
  8. (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 满足约束。