問題一覧 > 通常問題

No.2693 Sword

レベル : / AI推定難易度 : 850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 148
作問者 : tohohogisu / テスター : timi hibit_at 👑 seekworser m46bSDt
お気に入りにしたユーザー ProblemId : 10604 / 自分の提出
問題文最終更新日: 2024-03-21 21:55:16
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 423 (Asakatsu Presents 3) (順位表) の他の問題:

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)
Find the maximum attack power of the sword when Kamikazee equips exactly $K$ items.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。