#5050. 「JOISC 2025 Day3」勇者比太郎 3

题目译自 JOISC 2025 Day3 T1 「勇者ビ太郎 3 / Bitaro the Brave 3」

题目描述

勇者比太郎即将挑战一场守护村庄免受怪兽侵袭的防御战。这场战斗的难度可以用 $1$ 到 $L$ 的整数表示，你可以在挑战时自由选择。难度为 $\ell$ ($1 \leq \ell \leq L$) 时，怪兽的生命值（HP）将基于难度 $1$ 乘以 $\ell$ 倍。

防御战持续 $T$ 秒，期间会有 $N$ 只怪兽接连出现，编号从 $1$ 到 $N$。战斗开始后的 $t$ ($0 \leq t \leq T$) 秒称为时刻 $t$。怪兽 $i$ ($1 \leq i \leq N$) 在时刻 $S_i$ ($0 \leq S_i < T$) 出现，强度为 $P_i$，HP 为 $\ell \times H_i$（$\ell$ 为所选难度）。

战斗中，比太郎可以无限次执行以下操作：

• 从当前出现的怪兽中挑选一只，用 $1$ 秒攻击它，使其 HP 减少 $1$。若 HP 降至 $0$，怪兽被击败，无法再被攻击。

时刻 $T$ 时战斗结束，评价值按以下方式计算：

• 设时刻 $T$ 结束时，怪兽 $i$ ($1 \leq i \leq N$) 的剩余 HP 为 $h_i$，评价值为 $h_1 P_1 + h_2 P_2 + \cdots + h_N P_N$。

只有当评价值不超过任务设定的标准值 $m$ 时，比太郎才能完成任务。难度越高，奖励越丰厚，因此他想知道能完成任务的最大难度。但标准值 $m$ 事先未知，于是他决定针对 $Q$ 个候选标准值 $M_1, M_2, \ldots, M_Q$，分别求出能完成任务的最大难度。

给你防御战信息和候选标准值，编写程序判断每个标准值下任务是否可完成，若可行，计算最大难度。

输入格式

第一行包含三个整数 $N,L,T$。

接下来的 $N$ 行，每行包含三个整数 $S_i, H_i, P_i$。

接下来的一行，包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含一个整数 $M_i$。

输出格式

输出 $Q$ 行。第 $j$ ($1 \leq j \leq Q$) 行输出当 $m = M_j$ 时，能完成任务的最大难度。若任何难度都无法完成，输出 $0$。

样例 1

输入

2 2 10
0 9 2
8 5 1
3
0
20
40

输出

0
1
2

解释
在难度 $1$ 的防御战中，可以通过以下方式行动，达到评价分数 $4$。无法达到评价分数 $3$ 或更低。

时刻	事件
0	怪物 1（HP 9）出现。
0-8	对怪物 1 攻击 8 次。怪物 1 的 HP 从 9 减少到 1。
8	怪物 2（HP 5）出现。
8-9	对怪物 2 攻击 1 次。怪物 2 的 HP 从 5 减少到 4。
9-10	对怪物 1 攻击 1 次。怪物 1 的 HP 从 1 减少到 0。
10	怪物 1 被击败。
	防御战结束。评价分数为 $0 \times P_{1} + 4 \times P_{2} = 4$。

在难度 $2$ 的防御战中，可以通过以下方式行动，达到评价分数 $26$。无法达到评价分数 $25$ 或更低。

时刻	事件
0	怪物 1（HP 18）出现。
0-8	对怪物 1 攻击 8 次。怪物 1 的 HP 从 18 减少到 10。
8	怪物 2（HP 10）出现。
8-10	对怪物 1 攻击 2 次。怪物 1 的 HP 从 10 减少到 8。
10	防御战结束。评价分数为 $8 \times P_{1} + 10 \times P_{2} = 26$。

此外，在此输入示例中，$L=2$，因此无法选择难度 $3$ 或以上的防御战。因此输出如下：

• 对于第 $1$ 个基准值 $M_{1}=0$，在任何难度下都无法完成任务，因此第一行输出 $0$。
• 对于第 $2$ 个基准值 $M_{2}=20$，最高能在难度 $1$ 下完成任务，因此第二行输出 $1$。
• 对于第 $3$ 个基准值 $M_{3}=40$，最高能在难度 $2$ 下完成任务，因此第三行输出 $2$。

这个样例满足子任务 $3,4,5,6,7,8$ 的限制。

样例 2

输入

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

输出

0

此样例满足所有子任务的限制。

样例 3

输入

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

输出

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

输出

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

输出

995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125

这个样例满足子任务 $5,6,7,8$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 6000$
• $1 \leq L \leq 10000000$
• $1 \leq T \leq 10^{18}$
• $0 \leq S_i < T$ ($1 \leq i \leq N$)
• $1 \leq H_i$ ($1 \leq i \leq N$)
• $1 \leq P_i$ ($1 \leq i \leq N$)
• $H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leq 10^{11}$
• $1 \leq Q \leq 1000000$
• $0 \leq M_j \leq 10^{18}$ ($1 \leq j \leq Q$)
• $M_1 < M_2 < \cdots < M_Q$
• 所有输入值为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1		$N \leq 30$, $Q = 1$, $M_1 = 0$, $L = 1$
2	3	$N \leq 30$, $Q = 1$, $M_1 = 0$
3	10	$N \leq 30$, $Q \leq 3$
4		$Q \leq 3$
5	35	$N \leq 30$
6	8	$N \leq 400$
7	20	$N \leq 1800$
8	13	无附加限制