No.777 Recursive Cake
タグ : / 解いたユーザー数 78
作問者 :
kakira9618
/ テスター :
37zigen
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
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
6The 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
7The maximum is $7$ kcal, obtained when making a recursive cake using the 1st cake.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。