시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4 초 | 512 MB | 41 | 5 | 5 | 41.667% |
There is a dungeon with N + 1 floors. There are M players in the dungeon. The floors are numbered from 1 to N + 1, starting from the entrance. The players are numbered from 1 to M.
A player uses energy to move from a floor to the next floor. The amount of energy a player uses is Ai if he moves from the floor i (1 ≤ i ≤ N) to the floor i + 1. As this is a one-way dungeon, the only possible moves between floors are from the floor i to the floor i + 1 for some i (1 ≤ i ≤ N).
In each of the floors from the floor 1 to the floor N, inclusive, there is a fountain of recovery. At the fountain of recovery in the floor i (1 ≤ i ≤ N), a player can increase his energy by 1 paying Bi coins. A player can use a fountain multiple times as long as he has needed coins. However, each player has a maximum value of his energy, and his energy cannot exceed that value even if he uses a fountain of recovery.
Now the player j (1 ≤ j ≤ M) is in the floor Sj. His current energy is 0. His maximum value of energy is Uj. He wants to move to the floor Tj. His energy cannot be smaller than 0 along the way. How many coins does he need?
Write a program which, given the information of the dungeon and the players, determines whether it is possible for each player to move to the destination so that his energy does not become smaller than 0 along the way. If it is possible to move, the program should calculate the minimum number of coins he needs.
Read the following data from the standard input. Given values are all integers.
N M A1 · · · AN B1 · · · BN S1 T1 U1 . . . SM TM UM
Write M lines to the standard output. The j-th line (1 ≤ j ≤ M) should contain the minimum number of coins the player j needs to move to the floor Tj. If it is impossible for the player j to move to the floor Tj, output −1 instead.
번호 | 배점 | 제한 |
---|---|---|
1 | 11 | N ≤ 3 000, M ≤ 3 000. |
2 | 14 | U1 = U2 = · · · = UM. |
3 | 31 | Tj = N + 1 (1 ≤ j ≤ M). |
4 | 44 | No additional constraints. |
5 4 3 4 1 1 4 2 5 1 2 1 1 6 3 1 6 4 3 5 1 2 5 9
-1 29 3 22
Since the maximum value of energy of the player 1 is 3, the player 1 cannot move from the floor 2 to the floor 3. Hence the first line of output is −1.
On the other hand, the maximum value of energy of the player 2 is 4. The player 2 can move to the floor 6 by the following way.
In total, the player 2 pays 29 coins. Since it is impossible for the player 2 to move to the floor 6 by paying less than 29 coins, the second line of output is 29.
10 10 1 8 9 8 1 5 7 10 6 6 10 10 2 8 10 3 9 8 3 7 2 11 28 5 11 28 7 11 28 1 11 18 3 11 18 8 11 18 4 11 11 6 11 11 10 11 11 9 11 5
208 112 179 248 158 116 234 162 42 -1
20 20 2 3 2 11 4 6 9 15 17 14 8 17 3 12 20 4 19 8 4 5 19 3 18 2 13 7 5 19 10 1 12 8 1 15 20 1 13 2 18 6 12 15 67 7 15 18 16 17 14 9 21 97 1 19 43 3 18 31 16 20 70 7 20 28 1 16 61 3 5 69 9 10 15 2 13 134 11 19 23 16 20 14 5 21 16 15 20 11 7 11 54 7 16 16 13 17 10 3 15 135
151 591 4 284 339 517 35 581 254 58 -1 178 519 -1 -1 -1 219 -1 -1 214