Pyramides – Regional event 2010

Level 3

ÉNONCÉ

Cet exercice permettra à Joseph Marchand de descendre une pyramide aux marches glissantes sans se fracturer un os.

Chaque case est dotée d'un degré d'adhérence. Il est donc dans l'intérêt de Joseph de passer par le chemin où il a le moins de chances de glisser.

Son escalier est cependant assez particulier : en effet, lorsque Joseph se trouve sur une case, il ne peut descendre que sur la case en bas à gauche ou sur la case en bas à droite.

ENTRÉE

  • Un entier N correspondant à la hauteur de la pyramide.
  • (N * (N + 1)) / 2 entiers correspondants au degré d'adhérence de chaque case.

SORTIE

  • Un entier correspondant au maximum de la somme des degrés d'adhérence pour parcourir la pyramide de haut en bas.

CONTRAINTES

  • N sera plus petit ou égal à 100
  • L'adhérence de chaque case sera comprise entre 0 et 1000 (bornes incluses)

Runtime constraints

Maximum memory usage
50000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
2
71 849 973
Sample output
1044
Sample input
3
811 740 702 946 380 362
Sample output
2497

Submit your solution

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