問題一覧 > 通常問題

No.777 Recursive Cake

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 78
作問者 : kakira9618 / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 2476 / 自分の提出
問題文最終更新日: 2018-12-03 23:55:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:

Problem Statement

Tomorrow is Christmas. You have bought $N$ cakes for the Christmas party.
The $i$-th cake is a rectangular cuboid with a depth of $A_i$ cm, a width of $B_i$ cm, and a height of $10$ cm, and its calorie content is $C_i$ kcal.
Using the cakes you have as ingredients, you want to make a "recursive cake" with as many calories as possible.

A recursive cake is defined recursively as follows.

  • A single cake
  • A recursive cake with one more cake placed on its top face without rotation, where the added cake has a depth and a width smaller than the depth and the width of the top face
    (that is, when the upper cake is the $i$-th cake and the lower cake is the $j$-th cake, cakes are placed so that $A_i < A_j$ and $B_i < B_j$ hold)

The calories of a recursive cake are the total calories of the cakes that compose it.

Find the maximum calories [kcal] of a recursive cake you can make.

Input

$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$ are integers
The input is fairly large, so be careful with I/O.

Output

Print the maximum calories [kcal] of a recursive cake you can make on the first line. Print a newline at the end.

Subtasks

This problem has no subtask scoring, but the test cases are divided into the following categories.

  • $1\leq N\leq 16$ and $C_i = 1$
  • $1\leq N\leq 16$
  • $1\leq N\leq 2000$ and $C_i = 1$
  • $1\leq N\leq 2000$
  • $1\leq N\leq 200000$ and $C_i = 1$
  • $1\leq N\leq 200000$ (full score)

Sample

Sample 1
Input
3
4 7 1
5 9 1
8 5 1
Output
2

Using the 1st and 2nd cakes, you can make a recursive cake of $1 + 1 = 2$ kcal, and this is the maximum.
You can also make a recursive cake using the 3rd cake, but in this case it has $1$ kcal, which is not the maximum.

Sample 2
Input
4
4 7 2
5 9 3
8 5 4
10 10 2
Output
7

Using the 1st, 2nd, and 4th cakes, you can make a recursive cake of $2 + 3 + 2 = 7$ kcal, and this is the maximum.
You can also make a recursive cake using the 3rd and 4th cakes, but in this case it has $4 + 2 = 6$ kcal, which is not the maximum.

Sample 3
Input
4
4 7 1
5 9 2
8 5 4
10 10 2
Output
6
The maximum is $4 + 2 = 6$ kcal, obtained when making a recursive cake using the 3rd and 4th cakes.

Sample 4
Input
3
5 5 7
5 7 5
7 5 5
Output
7
The maximum is $7$ kcal, obtained when making a recursive cake using the 1st cake.

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