| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 31 | 13 | 12 | 57.143% |
One Saturday Luka woke up from an afternoon nap and remembered: today is COCI! There was only one thing that he needed to do before the contest: raise the blinds.
Luka has $n$ blinds in his room, where the $i$-th one is lowered by $a_i$ centimeters from the top of the window. He can raise the blinds in two ways:
The speed at which the blinds are raised with a button is defined as follows: If all blinds are still rising, each will rise by 1ドル$ centimeter in s seconds. If $r$ blinds have already been risen to the top that slows down the system. Then it will take $s + k \cdot r$ seconds for all the remaining blinds to rise by 1ドル$ centimeter.
COCI is about to start, and Luka wants to raise his blinds as soon as possible. Meanwhile, his brother Marin entered the room and asked him $q$ questions: What is the minimum time you need to raise the blinds so that they are all lowered by at most $h$ centimeters? Marin is interested in the answer for each question considering the initial state of the blinds.
They realized that there is not enough time to think about it before COCI. Fortunately, the problem has just appeared here as well! Help them solve it!
Note: Luka will always raise the blind by an integer value of centimeters.
The first line contains integers $n,ドル $t,ドル $s$ and $k$ (1ドル ≤ n, t, s ≤ 10^5,ドル 0ドル ≤ k ≤ 10^5$), the number of blinds, the time required to raise a blind manually, the time required to raise a blind with a button and the slowing factor of parallel raising.
The second line contains $n$ integers $a_i$ (0ドル ≤ a_i ≤ 10^5$), the initial state of blinds.
The third line contains integer $q$ (1ドル ≤ q ≤ 10^5$), number of questions.
The fourth line contains $q$ integers $h_i$ (0ドル ≤ h_i ≤ 10^5$), required maximal blind height.
In first and only line print $q$ numbers, $i$-th of them is minimum time for raising the blinds such that they are lowered by at most $h_i$ centimeters.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 16 | $n, q, a_i , h_i ≤ 100$ |
| 2 | 26 | $k = 0$ |
| 3 | 32 | $q = 1$ |
| 4 | 36 | No additional constraints. |
3 2 5 1 2 2 4 3 2 0 1
4 14 9
To have all blinds lowered by at most 2ドル$ centimeters, Luka needs to manually raise the third blind by 2ドル$ centimeters. The quickest way to do this is to raise it manually. This will take him 4ドル$ seconds.
2 3 4 0 3 1 3 3 2 0
0 3 10
If all blinds need to be fully raised, Luka can first raise the third blind by 2ドル$ centimeters manually. Now he can press the button and let the blinds rise in parallel by 2ドル$ centimeters. In total, that will take 4ドル + 10 = 14$ seconds.
4 3 10 3 2 4 5 6 3 4 3 0
9 18 47
Similarly, if the blinds need to be lowered by at most 1ドル$ centimeter, Luka will first raise the third blind by 2ドル$ centimeters, and then raise all blinds together by 1ドル$ centimeter. The total time for raising will be 9ドル$ seconds.