Singeries – Épreuve régionale 2019

Niveau 7

É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$

Contraintes d'exécution

Utilisation mémoire maximum
50000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
9
3
0 -4 -2 -5 3 1 1 4 5
Exemple de sortie
3
Commentaire

Le seul moment de la course où le singe reste dans un couloir de largeur 3 pendant 3 mètres est mis en valeur par les deux lignes jaunes.

Exemple d'entrée
22
2
0 1 2 2 3 3 3 1 0 5 3 3 5 0 1 3 3 3 2 2 1 0
Exemple de sortie
6
Commentaire

Le participant reste deux fois dans un couloir de 2 mètres de large pendant 6 mètres.

Exemple d'entrée
22
1
0 -1 -2 -2 -1 -2 -3 -2 -2 -3 -4 -4 -3 -2 -2 -3 -2 -1 -2 -2 -1 0
Exemple de sortie
4
Commentaire

Le participant reste deux fois dans un couloir de 1 mètre de large pendant 4 mètres.