3494 Largest Submatrix of All 1’s

原文

時間制限:5000ミリ秒
ケース別時間制限:2000ミリ秒
メモリ制限:131072KB

最大の全要素が1の部分行列

問題

m行n列の、要素が0か1だけの行列が与えられたとき、全要素が1である部分行列のうち最大のものはどれか。ここで、「最大」とは、要素が一番多いということとする。

入力

入力は、複数のテストケースからなる。
各テストケースは、mとn(1<=m,n<=2000)を含む行で始まる。その後には、行主体の順番で、m行の各行にn個ずつ行列の要素(0か1)が書かれている。入力の最後にはEOFがある。

出力

各テストケースについて、全要素が1である部分行列のうち最大のものの要素の数を出力しなさい。もし全要素が0である行列を与えられたら、0と出力しなさい。

入力例

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

出力例

0
4

出典

POJ Founder Monthly Contest – 2008.01.31, xfxyjwf