AT_joigsp2025_h 勇者ビ太郎 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$ 到达时，防卫战结束，接着计算防卫战的**评价值**。 - 用 $h_i$ 表示时刻 $T$ 后第 $i$ 只怪物（$1 \leq i \leq N$）剩余的 HP，则评价值为 $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.（$5$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$，$L = 1$。 2.（$10$ 分）$N \leq 30$，$Q = 1$，$M_1 = 0$。 3.（$14$ 分）$N \leq 30$，$Q \leq 3$。 4.（$10$ 分）$Q \leq 3$。 5.（$33$ 分）$N \leq 30$。 6.（$7$ 分）$N \leq 400$。 7.（$16$ 分）$N \leq 1\,800$。 8.（$5$ 分）无额外限制。 --- ### 样例说明 1 当难度为 $1$ 时，可以按以下方式操作，使评价值为 $4$，无法达成 $3$ 或以下： 时刻 事件 0 怪物1（HP9）出现。 0-8 攻击怪物1，总共8次；其HP由9降到1。 8 怪物2（HP5）出现。 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（HP18）出现。 0-8 攻击怪物1，总共8次；其HP由18降到10。 8 怪物2（HP10）出现。 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 翻译