Montée des eaux – Qualification 2016

Level 2

Énoncé

Le grand conseil des Prolosaures, un groupe plus malin que la plupart de leurs congénères, cherche un moyen de calculer le volume gagné par la mer lors du déluge.

On vous donne une liste de nombres représentant les altitudes des différentes montagnes qui composent le continent ainsi que l’altitude globale atteinte par la montée des eaux. Écrivez un programme qui indique le volume total de l’eau au-dessus des zones inondées, sachant que la surface du sommet de chaque montagne vaut 1. Par exemple, si l'altitude d'une montagne est 20 et que l'altitude de l'eau est 23, alors cette montagne contribue pour un volume de 3 unités (voir exemples).

Entrée

L’entrée comprendra :

  • un entier relatif h correspondant à l’altitude atteinte par la mer ;
  • sur la ligne suivante, un entier naturel non nul N correspondant au nombre de montagnes ;
  • sur la ligne suivante, N entiers relatifs yi séparés par des espaces, représentant l’altitude de chaque montagne.

Sortie

Vous afficherez en sortie :

  • Le volume total V d’eau au-dessus des terres submergées.

Contraintes

  • -100 000 ≤ h ≤ 100 000 ;
  • 1 ≤ N ≤ 10 000 ;
  • -100 000 ≤ yi ≤ 100 000 ;
  • 0 ≤ V ≤ 100 000 000.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
500 milliseconds

Input/output samples

Sample input
-91
13
-41 -47 -52 -57 -74 -77 -23 -14 -56 2 -74 -40 -59
Sample output
0
Note

Ici, aucune terre n'est recouverte, le volume d'eau est donc nul.

Sample input
-42
12
-53 35 -44 -55 -47 -65 42 -25 -6 78 -7 -79
Sample output
91
Note

Ici, 91 unités d'eau recouvrent les terres. Par exemple, l'eau au-dessus de la première montagne contribue pour 11 unités.

Submit your solution

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