No.2693 Sword
タグ : / 解いたユーザー数 148
作問者 :
timi
hibit_at
👑 Problem Statement
Kamikazee the Grass, the protagonist of a certain game world, has a sword.
The attack power of the sword is currently a positive integer $P$.
Kamikazee also has $N$ items.
Equipping the $i$-th item gives the following effect:
- If $T_i$ $=$ $1$, the attack power increases by exactly $B_i$
- If $T_i$ $=$ $2$, the attack power is multiplied by $2$ (the value of $B_i$ is not used)
However, if it exceeds $10^{18}$, print
-1.The effects of the items are applied in ascending order of $i$. See the sample cases for details.
Input
$N\ P\ K$ $T_1\ B_1$ $T_2\ B_2$ $\vdots$ $T_N\ B_N$
- All input values are integers
- $1 \leq K \leq N \leq 1000$
- $1 \leq P \leq 10^{18}$
- $1 \leq T_i \leq 2$
- If $T_i$ is $1$, then $1 \leq B_i \leq 10^9$
- If $T_i$ is $2$, then $B_i = 0$
Output
Print the maximum attack power of the sword.
Sample
Sample 1
Input
3 4 2 1 2 1 3 2 0
Output
14
In this example, the attack power of the sword is initially $4$.
If the $2$-nd and $3$-rd items are equipped, the attack power of the sword changes as follows:
First, the effect of the $2$-nd item makes the attack power $7$.
Next, the effect of the $3$-rd item makes the attack power $14$.
This is the maximum attack power of the sword.
Sample 2
Input
5 1 3 2 0 2 0 1 4 1 4 1 4
Output
13
In this example, the attack power of the sword is initially $1$.
If the $3$-rd, $4$-th, and $5$-th items are equipped, the attack power of the sword changes as follows:
First, the effect of the $3$-rd item makes the attack power $5$.
Next, the effect of the $4$-th item makes the attack power $9$.
Finally, the effect of the $5$-th item makes the attack power $13$.
This is the maximum attack power of the sword.
Although it is not optimal, it is possible to equip the $1$-st, $2$-nd, and $3$-rd items.
In that case, the attack power of the sword becomes $8$. Note that the effects of the items are applied in ascending order of $i$.
Sample 3
Input
1 1 1 1 1
Output
2
In this example, there is only $1$ kind of item. Equipping it makes the attack power of the sword $2$, which is the maximum.
Sample 4
Input
2 999999999999999999 1 1 1 2 0
Output
-1
Equipping the $2$-nd item is optimal.
The sword's attack power $999999999999999999$ is doubled, but this exceeds $10^{18}$, so print $-1$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。