Plus grand rectangle de 0 – Qualification 2004

Niveau 2

Énoncé

Écrire une fonction qui prend en argument un tableau à deux dimensions rempli de 0 et de 1, et qui renvoie le nombre de cases du plus grand sous-tableau ne contenant que des 0.

On appelle sous-tableau, une zone rectangulaire, à l'intérieur du tableau d'origine, constituée d'un certain nombres de colonnes consécutives, et d'un certain nombre de lignes consécutives de ces colonnes.

Entrée

  • La première ligne de l'entrée contient deux entiers, séparés par une espace : $L$ et $C$, respectivement le nombre de lignes et de colonnes du tableau.

  • Chacune des $L$ lignes suivantes contient $C$ entiers (0 ou 1), séparés par des espaces : le contenu du tableau.

Sortie

Vous devez écrire un entier sur la sortie : le nombre de cases du plus grand sous-tableau ne contenant que des 0.

Contraintes

  • $1 \le L, C \le 1\,000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
5 4
0 1 0 1
1 0 0 0
0 0 0 0
0 0 0 0
1 1 0 1
Exemple de sortie
9