Prolego™ – Qualification 2013

Level 4

Énoncé

Vous possédez un jeu de N briques de dimensions (xi, yi, zi), ainsi qu'une machine vous permettant de dupliquer des briques. Vous pouvez orienter les briques comme bon vous semble, et les empiler pour former une tour de briques. Cependant, pour que la construction soit stable, vous ne pouvez poser une brique i sur une brique j que si la base de la brique du dessus est strictement incluse dans la base de la brique du dessous : elles ont respectivement des dimensions a × b et a' × b' telles que (a < a' et b < b') ou (a < b' et b < a'). Quelle est la hauteur de la plus grande tour que vous pouvez construire ?

Entrée

L'entrée comprendra :

  • un nombre N, le nombre de briques que vous avez au départ ;
  • sur les N lignes suivantes, les dimensions de chaque brique (xi, yi, zi).

Sortie

Vous afficherez en sortie :

  • la hauteur de la plus grande tour que vous pouvez construire.

Contraintes

  • 1 <= N <= 2 000
  • 1 <= xi, yi, zi <= 10 000 000
  • La hauteur de la plus grande tour ne dépasse jamais 100 000 000

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
1 4 1
2 5 3
4 4 4
Sample output
13
Sample input
4
1 4 8
1 8 5
2 7 2
3 6 6
Sample output
15
Note

La réponse est 15, par exemple on peut empiler :

  • (8, 5, hauteur 1)
  • (6, 3, hauteur 6)
  • (5, 1, hauteur 8) (une autre brique de même dimension que la première).

Submit your solution

You have to register or log in to be able to submit your solution.