Prologin
2024
Énoncé¶
Près du village de Joseph Marchand, il y a un ruisseau assez spécial : sa vitesse d'écoulement varie tout au long de la journée (en restant positive), et dès qu'elle atteint une certaine vitesse de seuil $M$, elle ne redescendera plus en-dessous de celle-ci le reste de la journée. Pour cette raison, ce ruisseau porte la dénomination de ruisseau progressif.
Joseph souhaite se convaincre de la véracité de la propriété du ruisseau. Une après-midi il décide de mesurer, à intervalles réguliers de temps, la vitesse d'écoulement du ruisseau.
Cependant, après expérience, il remarque que la propriété n'est pas toujours vérifiée en pratique, il vous montre ses résultats.
Vous, persuadé que le ruisseau est bien progressif, tentez d'expliquer à Joseph qu'il a très probablement fait des erreurs de mesure. Afin que votre argumentation soit crédible, calculez l'erreur minimale que Joseph a pu commettre en relevant les données.
L'erreur, par rapport à une solution acceptable, est la somme des différences absolues pour chaque instant de mesure.
Formellement, lors d'une après-midi, si le ruisseau est progressif alors :
- soit chaque vitesse mesurée $v_i$ est strictement inférieure au seuil $M$
- soit il existe $1 \le j \le N$ tel que pour tout $1 \le i \le j-1$ on a $v_i$ qui est strictement plus petit que $M$, et pour tout $j \le i\le N$ on a $v_i$ qui vaut au moins $M$.
Entrée¶
L'entrée comprendra deux lignes :
- La première ligne contiendra deux entiers $N$ et $M$, le nombre de mesures effectuées par Joseph, et le seuil $M$ du ruisseau.
- La seconde ligne contiendra $N$ entiers. Le i-ème d'entre eux, $v_i$, désignera la i-ème mesure de la vitesse.
Sortie¶
Vous afficherez un entier, la plus petite erreur effectuée par Joseph si le ruisseau était effectivement progressif (affichez 0 si la mesure de Joseph était initialement correcte).
Contraintes¶
- $1 \le N \le 500$
- $1 \le M \le 1\ 000$
- $0 \le v_i \le 1\ 000$
Contrainte de performance¶
- $1 \le N \le 200\ 000$