Manhattan maboul – Qualification 2019

Level 3

Énoncé

Ah Manhattan… Le quartier préféré de Haruhi ! Nombreux de ses amis sont d'ailleurs de passage à New-York et Haruhi aimerait les revoir depuis son dernier long voyage.

Adepte des finales Prologin, Haruhi a pour objectif de rencontrer en $M$ jours consécutifs un nombre maximal de ses amis. Pour cela elle a noté l'arrivée de tout le monde. À noter qu'il est possible que plusieurs amis soient présents un même jour.

Entrée

La première ligne contient deux entiers $N$ et $M$ correspondant respectivement au nombre d'amis passant par New-York, ainsi qu'au nombre de jours consécutifs que Haruhi peut utiliser pour rencontrer ses amis.

Sur la ligne suivante $N$ entiers, représentant un jour où un des amis de Haruhi est à Manhattan.

Sortie

Le nombre d'amis maximum que Haruhi peut revoir en $M$ jours consécutifs.

Contraintes

  • $1 \le N \le 100$
  • $1 \le M \le 36$
  • $1 \le jour \le 10^6$

Contraintes de performance

  • $1 \le N \le 10^6$
  • $1 \le M \le 10^5$

Runtime constraints

Maximum memory usage
20000 kilobytes
Maximum execution time
600 milliseconds

Input/output samples

Sample input
6 5
3 11 1 7 6 12
Sample output
3
Note

Haruhi peut rencontrer 3 de ses amis en 5 jours consécutifs.

Sample input
5 2
4 1 7 9 7
Sample output
3
Note

Dans le meilleur des cas, Haruhi peut croiser 3 de ses amis en 2 jours consécutifs en sélectionnant les 3 derniers de la liste.

Submit your solution

You have to register or log in to be able to submit your solution.