No.2693 Sword

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 148
作問者 :

tohohogisu / テスター :

timi

hibit_at 👑

seekworser

kikuepl

0 ProblemId : 10604 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2024-03-21 21:55:16

問題文

あるゲーム世界の主人公である草の Kamikazee は剣を持っています。
剣の攻撃力は現在正整数 $P$ となっています。
また Kamikazee は $N$ 個のアイテムを持っています。
$i$ 番目のアイテムを装備すると、以下のような効果を得ることができます：

$T_i$ $=$ $1$ のとき、攻撃力をちょうど $B_i$ 上げる
$T_i$ $=$ $2$ のとき、攻撃力を $2$ 倍にする（ $B_i$ の値は使わない）

Kamikazee がちょうど

K

個のアイテムを装備する場合、剣の攻撃力の最大値を求めてください。
ただし、それが

10^{18}

を超える場合は -1 を出力してください。
アイテムの効果は $i$ の昇順に適用されます。詳しくはサンプルケースを参照してください。

入力

 $N\ P\ K$ 
 $T_1\ B_1$ 
 $T_2\ B_2$ 
 $\vdots$ 
 $T_N\ B_N$

入力はすべて整数
$1 \leq K \leq N \leq 1000$
$1 \leq P \leq 10^{18}$
$1 \leq T_i \leq 2$
$T_i$ が $1$ のとき $1 \leq B_i \leq 10^9$
$T_i$ が $2$ のとき $B_i = 0$

出力

剣の攻撃力の最大値を出力してください。

サンプル

サンプル1

入力

出力

この例では、最初は剣の攻撃力は $4$ です。
$2$ 番目と $3$ 番目のアイテムを装備すると、剣の攻撃力は以下のように推移します：
まず、 $2$ 番目のアイテムの効果によって攻撃力が $7$ となります。
次に、 $3$ 番目のアイテムの効果によって攻撃力が $14$ となります。
これが剣の攻撃力の最大値です。

サンプル2

入力

出力

この例では、最初は剣の攻撃力は $1$ です。
$3$ 番目、 $4$ 番目、そして $5$ 番目のアイテムを装備すると、剣の攻撃力は以下のように推移します：：
まず、 $3$ 番目のアイテムの効果によって攻撃力が $5$ となります。
次に、 $4$ 番目のアイテムの効果によって攻撃力が $9$ となります。
最後に、 $5$ 番目のアイテムの効果によって攻撃力が $13$ となります。
これが剣の攻撃力の最大値です。
最適解ではありませんが、 $1$ 番目、 $2$ 番目、そして $3$ 番目のアイテムを装備することができます。
その場合、剣の攻撃力は $8$ となります。アイテムの効果が適用されるのは $i$ の昇順であることに注意してください。

サンプル3

入力

1 1 1
1 1

出力

この例では、アイテムが $1$ 種類しかありません。それを装備することで、剣の攻撃力は $2$ となり、これが最大値です。

サンプル4

入力

2 999999999999999999 1
1 1
2 0

出力

-1

$2$ 番目のアイテムを装備するのが最適解です。
剣の攻撃力 $999999999999999999$ が倍増されますが、これは $10^{18}$ を超えるので、 $-1$ を出力してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。