問題一覧 > 通常問題

No.2957 Combo Deck Builder

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 31
作問者 : 👑 binapbinap / テスター : 👑 p-adicp-adic ecotteaecottea hamamuhamamu
3 ProblemId : 11235 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-11-02 20:01:52

問題文

あなたはカードゲームをしています。カード $1$ からカード $N$ までの $N$ 枚のカードを手札に持っており、これらを用いて敵に攻撃します。

カード $i$ ( $1\leq i \leq N$ ) の効果は次の通りです。

・(このカードを含めずに)既に $C_i$ 枚以上のカードを使用していたならば敵に $X_i$ のダメージを与える。

・そうでないならば敵に $Y_i$ のダメージを与える。

$N$ 枚のカードから任意の枚数を選び、任意の順で $1$ 回ずつ使用します。与えられる合計ダメージの最大値を求めてください。

制約

・ $1\leq N \leq 2\times 10^5$

・ $0\leq C_i \leq N$ ( $1\leq i \leq N$ )

・ $1\leq X_i,Y_i \leq 10^9$ ( $1\leq i \leq N$ )

・入力は全て整数。

入力

$N$
$C_1$ $X_1$ $Y_1$
$\vdots$
$C_N$ $X_N$ $Y_N$

出力

答えを $1$ 行で出力してください。

サンプル

サンプル1
入力
3
0 4 3
2 3 5
2 8 2
出力
17

各カードの効果はそれぞれ以下の通りです。

・「既に使用したカードが $0$ 枚以上なら $4$ ダメージ。そうでないなら $3$ ダメージ」(カード $1$ )

・「既に使用したカードが $2$ 枚以上なら $3$ ダメージ。そうでないなら $5$ ダメージ」(カード $2$ )

・「既に使用したカードが $2$ 枚以上なら $8$ ダメージ。そうでないなら $2$ ダメージ」(カード $3$ )

カード1、カード2、カード3をこの順に使用すると $17$ のダメージを与えることができます。

・既に使用したカードは $0$ 枚以上である。 $4$ のダメージを与える。(カード $1$ )

・既に使用したカードは $2$ 枚未満である。 $5$ のダメージを与える。(カード $2$ )

・既に使用したカードは $2$ 枚以上である。 $8$ のダメージを与える。(カード $3$ )

$18$ 以上のダメージを与える方法はありません。

サンプル2
入力
6
2 13 14
2 5 13
2 17 16
4 13 9
2 10 16
4 8 9
出力
81

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