oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pokecubes Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pokecubes.html

Problem #3: PokéCubes

Pokéballs sold in Pokémarts are round in shape, but Little Joseph wanted to be different from the rest. In his own home laboratory, he has come up with a new invention for catching Pokémon: Pokécubes!

However, as Little Joseph is a very sloppy person, all his Pokécubes are of different sizes and dimensions, and most of the times not cubes. Also, his Pokécubes are not as powerful as Pokéballs and can shrink into the cute marble-sized Pokéball for easy storage. Hence, Little Joseph is having problems carrying around all his Pokécubes in his bag.

One day, PokéMaster Hubert gave Little Joseph a great idea: Little Joseph can pack smaller Pokécubes into the big Pokécubes and thus would not take as much space. When packing his Pokécubes, he starts with the smallest Pokécube and puts it entirely inside a larger one. Then he takes that Pokécube and puts it inside another, and so on. Your task as a PokéProgrammer is to find out the largest number of Pokécubes that can be fit in this way.

Note that Little Joseph can set the inner Pokécube on any side inside the larger Pokécube. So Pokécube A might not fit inside Pokécube B in one orientation, but would in another. To simplify things, we'll ignore thickness of the Pokécube sides. So, a 3 by 4 by 5 Pokécube will fit inside of another 3 by 4 by 5 Pokécube.

Input

The first line of the input will be an integer n (n ≤ 50) representing the number of Pokécubes Little Joseph has, followed by n number of lines with three integers x, y and z representing the dimensions of the Pokécube.

Output

A single line with an integer representing the maximum number of Pokécubes Little Joseph can pack in this way.

Sample Input

5
3 4 5
5 6 3
1 4 10
4 4 4
6 6 5

Sample Output

3

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110071s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o pokecubes -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.