구획
시간 제한3초메모리 제한512 MB
0은 경작지, 1은 황무지인 n x n 격자가 주어질 때 0으로만 이루어진 가장 큰 직사각형의 넓이를 구해 출력한다. n은 최대 2000이다.
문제
한 변의 길이가 인 정사각형 모양의 밭이 있다. 이 밭은 한 변의 길이가 인 개의 단위 정사각형 칸으로 나뉜다. 각 칸은 경작할 수 있는 땅(경작지)이거나 쓸 수 없는 땅(황무지) 중 하나이다.
이 밭에서 하나의 구획을 정하려고 한다. 구획은 직사각형이어야 하며, 경작지 칸만으로 이루어져야 한다. 구획의 넓이는 그 직사각형의 넓이와 같다. 넓이가 가장 큰 구획을 찾아야 한다.
다음을 수행하는 프로그램을 작성하라.
- 표준 입력에서 밭의 정보를 읽는다.
- 넓이가 가장 큰 구획의 넓이를 계산한다. (그러한 구획이 여러 개일 수도 있다.)
- 계산한 넓이를 표준 출력에 쓴다.
입력
첫째 줄에 정수 이 주어진다. ()
이어지는 개의 줄에는 밭의 각 행을 이루는 칸들의 정보가 주어진다. 각 줄에는 또는 인 개의 숫자가 하나의 공백으로 구분되어 주어진다. 각 숫자는 그 행의 칸을 순서대로 나타내며, 은 경작지 칸을, 은 황무지 칸을 뜻한다.
출력
경작지로만 이루어진 가장 큰 직사각형 구획의 넓이를 첫째 줄에 정수 하나로 출력한다. 모든 칸이 황무지여서 어떤 구획도 만들 수 없으면 을 출력한다.