AT_joisp2025_g 勇者ビ太郎 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$ 时 $\ell \times H_i$。 防御战中，比太郎可以不限次数地进行如下操作： - 从当前出现的怪兽中选出一只，花费 $1$ 秒对其攻击一次，该怪兽的 HP 减少 $1$。HP 变为 $0$ 的怪兽会被击败，之后无法再对其进行攻击。 当时刻 $T$ 到来时防御战结束，随后按如下方式计算防御战的**评价值**： - 记在时刻 $T$ 结束后，编号为 $i$ 的怪兽的 HP 为 $h_i$，则评价值为 $h_1 P_1 + h_2 P_2 + \dots + h_N P_N$。 当且仅当评价值不超过任务规定的基准值 $m$ 时，比太郎才能完成该任务。 由于完成高难度的任务可获得更丰厚的奖励，比太郎想求出自己能完成任务的最大难度。然而，基准值事先未知，因此比太郎需要针对 $Q$ 个候选基准值 $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 \leq j \leq Q$）输出，当 $m = M_j$ 时，能够完成任务的最大难度。如果任何难度下都无法完成任务，则输出 `0`。

## 小子任务 1. （$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. （$10$ 分）$Q \leq 3$。 5. （$35$ 分）$N \leq 30$。 6. （$8$ 分）$N \leq 400$。 7. （$20$ 分）$N \leq 1\,800$。 8. （$13$ 分）无附加限制。 --- ## 样例解释 1 在难度 $1$ 的防御战中，可以按下述方式行动，取得评价值 $4$，无法取得评价值 $3$ 或以下。 时刻 事件 $0$ 怪兽 $1$（HP $9$）出现。 $0$-$8$ 对怪兽 $1$ 攻击 $8$ 次，HP 从 $9$ 减至 $1$。 $8$ 怪兽 $2$（HP $5$）出现。 $8$-$9$ 对怪兽 $2$ 攻击 $1$ 次，HP 从 $5$ 减至 $4$。 $9$-$10$ 对怪兽 $1$ 攻击 $1$ 次，HP 从 $1$ 减至 $0$。 $10$ 怪兽 $1$ 被打倒。 $10$ 防御战结束，评价值为 $0 \times P_1 + 4 \times P_2 = 4$。 而在难度 $2$ 的防御战中，可以如下行动，获得评价值 $26$，无法取得评价值 $25$ 或以下。 时刻 事件 $0$ 怪兽 $1$（HP $18$）出现。 $0$-$8$ 对怪兽 $1$ 攻击 $8$ 次，HP 从 $18$ 减至 $10$。 $8$ 怪兽 $2$（HP $10$）出现。 $8$-$10$ 对怪兽 $1$ 攻击 $2$ 次，HP 从 $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 该输入符合小子任务 $2, 3, 4, 5, 6, 7, 8$ 的约束。 --- ## 样例解释 4 该输入符合小子任务 $5, 6, 7, 8$ 的约束。 --- ## 样例解释 5 该输入符合小子任务 $5, 6, 7, 8$ 的约束。 # 数据范围与限制 - $1 \leq N \leq 6\,000$。 - $1 \leq L \leq 10\,000\,000$。 - $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 1\,000\,000$。 - $0 \leq M_j \leq 10^{18}$（$1 \leq j \leq Q$）。 - $M_1 < M_2 < \cdots < M_Q$。 - 输入的所有数均为整数。 由 ChatGPT 5 翻译