問題一覧 > 通常問題

No.777 再帰的ケーキ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 73
作問者 : kakira9618kakira9618 / テスター : 37zigen37zigen
2 ProblemId : 2476 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-03 23:55:53

問題文

明日はクリスマスです。あなたは、クリスマスパーティのためのケーキを$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 が最大です。

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