| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 (추가 시간 없음) | 2048 MB | 21 | 3 | 3 | 42.857% |
You just created a new character in your favourite role-playing game and now have to decide how to skill him.
The two skill attributes to be chosen are: damage per hit and hits per second. Damage per hit is the amount of damage you deal with a single hit, while hits per second is the number of hits you can make in one second. Initially, both skill attributes are set at 0ドル$. You have $k$ skill points to distribute as you want; in other words, you can choose the values of the two skills so that they are positive integers with sum at most $k$.
The tutorial of the game (the boring part you want to finish as soon as possible) consists of $n$ monsters to be killed one after the other. The $i$-th monster has $h_i$ health points, i.e., it dies after you have inflicted at least $h_i$ damage.
How can you assign the two skill attributes to minimize the time necessary to kill all the $n$ monsters?
The first line contains two integers $n$ and $k$ (1ドル ≤ n ≤ 200,円 000,ドル 2ドル ≤ k ≤ 200,円 000$) — the number of enemies and the number of skill points.
The second line contains $n$ integers $h_i$ (1ドル ≤ h_i ≤ 10^{13}$) — the health of the $i$th enemy.
Print two positive integers $x$ and $y$ (1ドル ≤ x, y$ and $x + y ≤ k$) — the number of skill points you want to invest in damage per hit and hits per second. If there are multiple optimal solutions, print any of them.
1 7 14
3 4
There is only one monster and you have 7ドル$ skill points to distribute. If you make 3ドル$ damage per hit, you will need 5ドル$ hits to kill it. If you do 4ドル$ hits per second, you will need 1ドル.25$ seconds to beat the monster. There is no way to beat the monster faster than this.
4 9 1 2 3 4
4 5
You will need one hit for each monster and a total time of 0ドル.8$ seconds if you distribute 4ドル$ skill points on damage per hit and the remaining 5ドル$ points on hits per second.
5 13 3 4 5 6 7
7 6