Plus grand rectangle de 0 – Qualification 2004

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

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
10000 milliseconds

Input/output samples

Sample input
5 4
0 1 0 1
1 0 0 0
0 0 0 0
0 0 0 0
1 1 0 1
Sample output
9

Submit your solution

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