Prologin
2025
Énoncé¶
Les singes de la savane occupent leurs journées en organisant des concours du jeu de la toupie. Le concept est simple: un participant effectue 42 tours sur lui-même puis doit courir en ligne droite sur une piste de course de $n$ mètres.
L'objectif du jeu est de réussir à courir suffisamment droit pendant le plus longtemps possible. Pour cela, on mesure tous les mètres le décalage d'un participant avec le centre de la piste de course. Le but d'un candidat est que pendant un tronçon de sa course le plus long possible, sa trajectoire soit moins large que $d$ mètres.
Il faut être stratégique car le but n'est pas de rester proche du centre de la piste de course, mais qu'à un moment de sa course, le participant réussisse à maintenir un écart presque constant.
Calculez le score du candidat dont la trajectoire vous est donnée.
Entrée¶
L'entrée comprendra:
- Un entier sur la première ligne: la longueur $n$ de la piste de course.
- Un entier sur la seconde ligne: l'écart maximal pour qu'un tronçon soit pris en compte.
- Une liste de $n$ entiers sur la ligne suivante: pour chaque mètres $i$ que le participant a parcouru, son écart $a_i$ au centre de la piste à cet instant, en mètres.
Sortie¶
Affichez un entier : la plus grande longueur de course pendant laquelle le participant a réussi à avoir une trajectoire moins large que $d$ mètres.
Contraintes¶
- $1 \le n \le 10^6$
- $1 \le d \le 2 \times 10^9$
- $-10^9 \le a_i \le 10^9$
