Maximum Square (UVa Live Archive North America - Southeast - 2010/2011)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4867

問題

すべての要素が1か0で構成されたN*M行列がある。その中の正方形で全て1で構成される最大の正方形の辺の長さを求めよ。
1<=N,M<=1000

解法

ヒストグラムの長方形の最大面積を使って求めた。正方形なので、もっと簡単なDPでもいける。