| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 9 | 2 | 2 | 100.000% |
Bitaro, the brave hero, is about to take on the Defense Battle quest to protect the village from monsters. The difficulty of the Defense Battle is represented by an integer between $1$ and $L$, inclusive, and this value can be chosen at the start of the challenge. In a Defense Battle of difficulty $ℓ$ ($1 ≤ ℓ ≤ L$), the HP of monsters is multiplied by $ℓ$ compared to that at difficulty $1$.
The Defense Battle lasts for $T$ seconds, and $N$ monsters will appear throughout the battle. Each monster is assigned a unique number from $1$ to $N$. Time $t$ ($0 ≤ t ≤ T$) refers to the moment $t$ seconds after the battle starts. Monster $i$ ($1 ≤ i ≤ N$) appears at time $S_i$ ($0 ≤ S_i < T$), has strength $P_i$, and its HP at difficulty $ℓ$ is given by $ℓ \times H_i$.
During the Defense Battle, Bitaro can perform the following action any number of times.
When time reaches $T$, the Defense Battle ends, and the penalty score is computed as follows.
If the penalty score is less than or equal to a threshold value $m$ specified by the quest, Bitaro successfully completes the quest.
Since higher difficulties yield better rewards, Bitaro wants to determine the highest difficulty level at which he can complete the quest. However, the threshold value is unknown in advance. Thus, Bitaro decides to determine the highest difficulty level at which he can complete the quest for each of $Q$ candidate threshold values $M_1, M_2, \dots , M_Q$.
Given the information about the Defense Battle and the candidate threshold values, write a program that determines whether the quest can be completed for each threshold value and, if possible, finds the maximum difficulty level at which the quest can be completed.
Read the following data from the standard input.
$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$
Write $Q$ lines to the standard output. In the $j$-th line ($1 ≤ j ≤ Q$), output the maximum difficulty level at which the quest can be completed when $m = M_j$. If the quest cannot be completed at any difficulty level, output 0 instead.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 1 | $N ≤ 30$, $Q = 1$, $M_1 = 0$, $L = 1$. |
| 2 | 3 | $N ≤ 30$, $Q = 1$, $M_1 = 0$. |
| 3 | 10 | $N ≤ 30$, $Q ≤ 3$. |
| 4 | 10 | $Q ≤ 3$. |
| 5 | 35 | $N ≤ 30$. |
| 6 | 8 | $N ≤ 400$. |
| 7 | 20 | $N ≤ 1\,800$. |
| 8 | 13 | No additional constraints. |
2 2 10 0 9 2 8 5 1 3 0 20 40
0 1 2
In the Defense Battle of difficulty $1$, the following actions can be taken to achieve a penalty score of $4$. It is not possible to achieve a penalty score of $3$ or lower.
| Time | Event |
|---|---|
| $0$ | Monster $1$ (HP $9$) appears. |
| $0$ – $8$ | Attack Monster $1$ a total of $8$ times. Monster $1$’s HP decreases from $9$ to $1$. |
| $8$ | Monster $2$ (HP $5$) appears. |
| $8$ – $9$ | Attack Monster $2$ once. Monster $2$’s HP decreases from $5$ to $4$. |
| $9$ – $10$ | Attack Monster $1$ once. Monster $1$’s HP decreases from $1$ to $0$. |
| $10$ | Monster $1$ is defeated. |
| $10$ | The Defense Battle ends. The penalty score is $0 \times P_1 + 4 \times P_2 = 4$. |
Additionally, in the Defense Battle of difficulty $2$, the following actions can be taken to achieve a penalty score of $26$. It is not possible to achieve a penalty score of $25$ or lower.
| Time | Event |
|---|---|
| $0$ | Monster $1$ (HP $18$) appears. |
| $0$ – $8$ | Attack Monster $1$ a total of $8$ times. Monster $1$’s HP decreases from $18$ to $10$. |
| $8$ | Monster $2$ (HP $10$) appears. |
| $8$ – $10$ | Attack Monster $1$ a total of $2$ times. Monster $1$’s HP decreases from $10$ to $8$. |
| $10$ | The Defense Battle ends. The penalty score is $8 \times P_1 + 10 \times P_2 = 26$. |
Furthermore, in this input example, since $L = 2$, it is not possible to choose a Defense Battle of difficulty $3$ or higher. Therefore, the output will be as follows:
0 on the first line.This sample input satisfies the constraints of subtasks 3, 4, 5, 6, 7, and 8.
3 1 100000000000 60000000000 30000000000 1 30000000000 45000000000 1 10000000000 10000000000 1 1 0
0
This sample input satisfies the constraints of all subtasks.
3 10000000 100000000 60000000 4 1 30000000 6 1 0 2 1 1 0
7000000
This sample input satisfies the constraints of subtasks 2, 3, 4, 5, 6, 7, and 8.
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
This sample input satisfies the constraints of subtasks 5, 6, 7, and 8.
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
This sample input satisfies the constraints of subtasks 5, 6, 7, and 8.