Rolete
레이팅 미적용의견: 0
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:
• He can start lifting any singular blind manually. With this method, it takes
him \(t\) seconds to raise the blind by 1 centimeter.
• He can press a button, which starts raising all blinds parallel at the same
speed.
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.
Subtask 1 (16 points): n, q, a_{i}, \(h_{i} \le 100\)
Subtask 2 (26 points): \(k = 0\)
Subtask 3 (32 points): \(q = 1\)
Subtask 4 (36 points): No additional constraints.
The first line contains integers \(n\), \(t\), \(s\) and \(k\) (\(1 \le n\), t, \(s \le 10^{5}\), \(0 \le k \le 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 \le a_{i} \le 10^{5}\)), the initial state of blinds.
The third line contains integer \(q\) (\(1 \le q \le 10^{5}\)), number of questions.
The fourth line contains \(q\) integers \(h@@RISE_MATH_BLOCK_0@@i \le 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} \le 100\) |
2 | 26점 | \(k = 0\) |
3 | 32점 | \(q = 1\) |
4 | 36점 | No additional constraints. |
3 2 5 1
2 2 4
3
2 0 14 14 92 3 4 0
3 1
3
3 2 00 3 104 3 10 3
2 4 5 6
3
4 3 09 18 47Clarification of the first example:
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.
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.
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.
평가 및 의견
Rolete
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Rolete