| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 118 | 18 | 13 | 12.745% |
Those events you attended on your arrival day were an exciting opportunity to become familiar again with the state of the (contemporary) art. And even more: The rumors you heard there revealed that the art collection you are interested in is stored in a secret underwater vault in the nearby Baltic Sea, owned by an old Lübeck grain merchant family! In memory of your past as an art thief, you decided to plan to break into this vault as a relaxing afternoon activity.*
To break into the vault, you want to use your newly acquired submarine. Unfortunately, your submarine will need a very specific amount of uplift $L$ when you try to escape from the crime scene. After all, you don’t want your submarine to crash into the bottom of the sea or float on the water surface where the police could catch you easily!
In order to plan your break-in accordingly, you need to know about the uplift of the art pieces in the vault. Skilled as you are, you were able to obtain relevant information.† For every possible uplift $\ell$ you now know how many art pieces $A_\ell$ with that uplift are stored in the vault.
Write a program that uses this information to either calculate the maximum number of art pieces you can steal such that their total uplift (obtained by summing the individual uplift of every stolen art piece) is exactly $L$ or to decide that this is impossible.
* A purely hypothetical heist, of course.
† It’s not your fault that their security system uses a weak hash algorithm, is it?
The first line of input contains two integers $M$ and $L,ドル meaning that the uplift of every art piece in the vault is between $-M$ and $M$ inclusive and that the total required uplift is $L$.
The next line contains 2ドルM + 1$ integers $A_{-M},ドル $\dots,ドル $A_M$ where $A_\ell$ describes the number of art pieces with uplift $\ell$ in the vault.
Your program should output a single line. This line should consist of an integer, the maximum number of art pieces you can steal such that their total uplift is exactly $L,ドル or the string impossible if there is no way to achieve this.
We always have 1ドル ≤ M ≤ 300,ドル $-10^{18} ≤ L ≤ 10^{18},ドル and 0ドル ≤ A_\ell ≤ 10^{12}$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | $M, A_\ell ≤ 50$ |
| 2 | 15 | $M, A_\ell ≤ 100$ |
| 3 | 20 | $M ≤ 30$ |
| 4 | 20 | $M ≤ 50$ |
| 5 | 20 | $M ≤ 100$ |
| 6 | 20 | No further constraints. |
2 5 2 3 1 1 4
9
3 5 3 1 0 2 0 0 2
impossible
1 5 0 0 6
5
In the first example, you can steal one art piece each with uplift $-2,ドル 0ドル$ and 1ドル$ respectively, two art pieces with uplift $-1,ドル and four art pieces with uplift 2ドル$. This results in a total of 1ドル + 1 +たす 1 +たす 2 +たす 4 =わ 9$ stolen art pieces with a total uplift of 1ドル ⋅ (-2) + 1 ⋅ 0 + 1 ⋅ 1 + 2 ⋅ (-1) + 4 ⋅ 2 = 5$ as required.
In the second example, it is impossible to steal art pieces such that their total uplift is 5ドル$.