Rendre le tableau non décroissant
On vous donne un tableau de
n entiers et vous devez le rendre non décroissant. Vous pouvez ajouter 1 à n’importe quel élément du tableau autant de fois que vous le souhaitez. Chaque ajout de 1 à un élément vous coûte 1 $. L’objectif est de rendre le tableau non décroissant en dépensant le moins possible. Saurez-vous calculer le coût minimum nécessaire pour effectuer cette transformation ?Entrée
La première ligne de l’entrée contient un entier
n (2 ≤ n ≤ ) – il s’agit du nombre d’éléments dans le tableau.La deuxième ligne de l’entrée contient
n entiers séparés par des espaces, ( ≤ ≤ ) – ces valeurs représentent les éléments du tableau.Sortie
Le programme doit afficher le coût minimal permettant de transformer le tableau en une suite non décroissante.
Exemples
Input | Output |
4
-2 3 1 0 | 5 |
5
1 2 3 4 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB