問題一覧 > 通常問題

No.2957 Combo Deck Builder

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

問題文

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

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

・（このカードを含めずに）既に CiC_i 枚以上のカードを使用していたならば敵に XiX_i のダメージを与える。

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

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

制約

・ 1≤N≤2×1051\leq N \leq 2\times 10^5

・ 0≤Ci≤N0\leq C_i \leq N ( 1≤i≤N1\leq i \leq N )

・ 1≤Xi,Yi≤1091\leq X_i,Y_i \leq 10^9 ( 1≤i≤N1\leq i \leq N )

・入力は全て整数。

入力

NN
C1C_1 X1X_1 Y1Y_1
⋮\vdots
CNC_N XNX_N YNY_N

出力

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

サンプル

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

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

・「既に使用したカードが 00 枚以上なら 44 ダメージ。そうでないなら 33 ダメージ」（カード 11 ）

・「既に使用したカードが 22 枚以上なら 33 ダメージ。そうでないなら 55 ダメージ」（カード 22 ）

・「既に使用したカードが 22 枚以上なら 88 ダメージ。そうでないなら 22 ダメージ」（カード 33 ）

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

・既に使用したカードは 00 枚以上である。 44 のダメージを与える。（カード 11 ）

・既に使用したカードは 22 枚未満である。 55 のダメージを与える。（カード 22 ）

・既に使用したカードは 22 枚以上である。 88 のダメージを与える。（カード 33 ）

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

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

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