No.777 再帰的ケーキ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 38
作問者 : kakira9618kakira9618 / テスター : 37zigen37zigen
1 ProblemId : 2476 / 出題時の順位表

問題文

明日はクリスマスです。あなたは、クリスマスパーティのためのケーキを$N$個買いました。
$i$ 個目のケーキの形は、奥行きが $A_i$ cm, 幅が $B_i$ cm, 高さが $10$ cm の直方体であり、カロリーは $C_i$ kcal です。
あなたは持っているケーキを材料にして、できるだけ高いカロリーをもつ"再帰的ケーキ"を作ろうと考えました。

再帰的ケーキの再帰的定義は以下のとおりです。

  • 1つのケーキからなるもの
  • 再帰的ケーキの最上面に、「最上面の奥行き・幅より小さな奥行き・幅を持つケーキ」を回転させずに1つのせたもの
    (つまり、上部のケーキを $i$ 個目、下部のケーキを $j$ 個目とすると、$A_i < A_j$ かつ $B_i < B_j$ が成り立つようにケーキをのせていく)

再帰的ケーキのカロリーは、再帰的ケーキを構成するケーキのカロリーの合計になります。

作ることのできる再帰的ケーキのカロリーの最大[kcal]を求めてください。

入力

$N$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
…
$A_N$ $B_N$ $C_N$

  • $1\leq N\leq 200000$
  • $1\leq A_i, B_i, C_i \leq 10^9$
  • $N, A_i, B_i, C_i$ は整数
入力数が多めなので、I/Oに注意してください。

出力

作ることのできる再帰的ケーキのカロリーの最大[kcal]を1行目に出力してください。 最後に改行してください。

部分点

この問題には部分点は設定されていませんが、入力ケースは以下の区分に分かれています。

  • $1\leq N\leq 16$ かつ $C_i = 1$
  • $1\leq N\leq 16$
  • $1\leq N\leq 2000$ かつ $C_i = 1$
  • $1\leq N\leq 2000$
  • $1\leq N\leq 200000$ かつ $C_i = 1$
  • $1\leq N\leq 200000$ (満点)

サンプル

サンプル1
入力
3
4 7 1
5 9 1
8 5 1
出力
2

1, 2個目のケーキを使って、$1 + 1 = 2$ kcal の再帰的ケーキを作ることが出来、これが最大です。
3個目のケーキを使って再帰的ケーキを作ることも出来ますが、この場合は $1$ kcal となって最大とはなりません。

サンプル2
入力
4
4 7 2
5 9 3
8 5 4
10 10 2
出力
7

1, 2, 4個目のケーキを使って、$2 + 3 + 2 = 7$ kcal の再帰的ケーキを作ることが出来、これが最大です。
3, 4個目のケーキを使って再帰的ケーキを作ることも出来ますが、この場合は $4 + 2 = 6$ kcal となって最大とはなりません。

サンプル3
入力
4
4 7 1
5 9 2
8 5 4
10 10 2
出力
6
3, 4個目のケーキを使って再帰的ケーキを作ったときの $4 + 2 = 6$ kcal が最大です。

サンプル4
入力
3
5 5 7
5 7 5
7 5 5
出力
7
1個目のケーキを使って再帰的ケーキを作ったときの $7$ kcal が最大です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。