No.2957 Combo Deck Builder
タグ : / 解いたユーザー数 30
作問者 : 👑
binap
/ テスター :
👑 
p-adic
ecottea
hamamu
問題文
あなたはカードゲームをしています。カード $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もしくは右上の雲マークをクリックしてアカウントを作成してください。