UOJ Logo Universal Online Judge

UOJ

#973. 【JOISC2025】勇者比太郎 3

附件下载 统计

比太郎在打防御战。防御战的难度用一个 [1,L] 的整数表示,这个值可以在任务开始时选择。在难度为 1L)的防御战中,怪物的生命值会是难度 1 时的 倍。

防御战持续 T 秒,期间会有 N 只怪物出现。每只怪物被分配一个从 1N 的唯一编号。时间 t0tT)指战斗开始后 t 秒的时刻。

怪物 i1iN)会在时间 Si0Si<T)出现,强度Pi,且在难度 下的生命值×Hi

在防御战中,比太郎可以无限次执行以下动作:

  • 选择当前在场的一只怪物并攻击它,这需要 1 秒的时间。怪物的生命值会减少 1。一旦怪物的生命值降为 0,它将被视为被击败并不再被攻击。

当时间到达 T 时,防御战结束,并按以下规则计算惩罚分:

  • hi 为时间 T 后怪物 i1iN)的剩余生命值。惩罚分为 h1P1+h2P2++hNPN

如果惩罚分小于等于任务指定的阈值 m,则比太郎成功完成任务。由于更高难度会带来更好的奖励,比太郎希望确定他能完成任务的最髙难度等级。但阈值 m 是未知的,因此比太郎决定针对 Q 个候选阈值 M1,M2,,MQ,分别找出能完成任务的最髙难度等级。

给定防御战的信息和候选阈值,请编写一个程序:对于每个阈值,判断任务是否可完成,并在可能的情况下找出可完成的最髙难度等级。

输入格式

  • N L T
  • S1 H1 P1
  • S2 H2 P2
  • SN HN PN
  • Q
  • M1
  • M2
  • MQ

输出格式

输出 Q 行。在第 j 行(1jQ),输出当 m=Mj 时能完成任务的最髙难度等级。如果在任何难度下都无法完成任务,则输出 0

样例一

input

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

output

0
1
2

explanation

在难度为 1 的防守战中,可以采取以下行动来达到 4 的惩罚分。无法达到 3 或更低的惩罚分。

时间 事件
0 怪物 1(生命值 9)出现。
08 攻击怪物 18 次。怪物 1 的生命值从 9 降至 1
8 怪物 2(生命值 5)出现。
89 攻击怪物 2 1 次。怪物 2 的生命值从 5 降至 4
910 攻击怪物 1 1 次。怪物 1 的生命值从 1 降至 0
10 怪物 1 被击败。
10 防守战结束。惩罚分为 0×P1+4×P2=4

此外,在难度为 2 的防守战中,可以采取以下行动来达到 26 的惩罚分。无法达到 25 或更低的惩罚分。

时间 事件
0 怪物 1(生命值 18)出现。
08 攻击怪物 18 次。怪物 1 的生命值从 18 降至 10
8 怪物 2(生命值 10)出现。
810 攻击怪物 12 次。怪物 1 的生命值从 10 降至 8
10 防守战结束。惩罚分为 8×P1+10×P2=26

此外,在此输入示例中,由于 L=2,无法选择难度 3 或更高的防御战。因此输出如下:

  • 对于第一个阈值 M1=0,无法在任何难度下完成任务,故第一行输出 0
  • 对于第二个阈值 M2=20,最多能在难度 1 下完成任务,故第二行输出 1
  • 对于第三个阈值 M3=40,最多能在难度 2 下完成任务,故第三行输出 2

该样例满足子任务 38 的限制。

样例二

input

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

output

0

explanation

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

样例三

input

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

output

7000000

explanation

该样例满足子任务 28 的限制。

样例四

input

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

output

6
8
10
12
13
15
16
18
19
20
20

explanation

该样例满足子任务 58 的限制。

数据范围

  • 1N6000
  • 1L10000000
  • 1T1018
  • 0Si<T1iN);
  • 1Hi1iN);
  • 1Pi1iN);
  • H1P1+H2P2++HNPN1011
  • 1Q1000000
  • 0Mj10181jQ);
  • M1<M2<<MQ
  • 输入的所有值均为整数。

子任务

  • Subtask 1 (1 pts)N30Q=1M1=0L=1
  • Subtask 2 (3 pts)N30Q=1M1=0
  • Subtask 3 (10 pts)N30Q3
  • Subtask 4 (10 pts)Q3
  • Subtask 5 (35 pts)N30
  • Subtask 6 (8 pts)N400
  • Subtask 7 (20 pts)N1800
  • Subtask 8 (13 pts):无额外限制。