Montée des eaux – Qualification 2016

É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 y_i 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 ≤ y_i ≤ 100 000 ;
• 0 ≤ V ≤ 100 000 000.