Hauteur de jetons – Qualification 2007

Niveau 2

Énoncé

Hauteur des jetons dans une grille de puissance 4.

On donne une grille de Puissance 4 : un tableau de taille N par M, de 0 et de 1, où les 1 sont des jetons, de couleur indifférenciée, et les 0 les trous ; vous devez trouver la hauteur maximale atteinte par les jetons.

Contraintes

  • 1 <= N <= 1000
  • 1 <= M <= 1000

Entrée

  • La première ligne de l'entrée contient les deux entiers N et M.
  • Les N lignes suivantes contiennent chacune M entiers : les jetons et trous de la grille.

Sortie

La sortie contient un entier : la hauteur maximale atteinte par les jetons.

Contraintes d'exécution

Utilisation mémoire maximum
3000 kilo-octets
Temps d'exécution maximum
750 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3 12
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 1 1 0
0 0 0 1 1 1 1 1 1 1 1 1
Exemple de sortie
2