No.777 再帰的ケーキ
タグ : / 解いたユーザー数 73
作問者 : kakira9618 / テスター : 37zigen
問題文
明日はクリスマスです。あなたは、クリスマスパーティのためのケーキを$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$ は整数
出力
作ることのできる再帰的ケーキのカロリーの最大[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
出力
63, 4個目のケーキを使って再帰的ケーキを作ったときの $4 + 2 = 6$ kcal が最大です。
サンプル4
入力
3 5 5 7 5 7 5 7 5 5
出力
71個目のケーキを使って再帰的ケーキを作ったときの $7$ kcal が最大です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。