問題一覧 > 通常問題

No.777 再帰的ケーキ

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

問題文

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

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

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

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

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

入力

N
A1 B1 C1
A2 B2 C2AN BN CN

  • 1N200000
  • 1Ai,Bi,Ci109
  • N,Ai,Bi,Ci は整数
入力数が多めなので、I/Oに注意してください。

出力

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

部分点

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

  • 1N16 かつ Ci=1
  • 1N16
  • 1N2000 かつ Ci=1
  • 1N2000
  • 1N200000 かつ Ci=1
  • 1N200000 (満点)

サンプル

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。