가장 큰 L자
시간 제한2초메모리 제한128 MB
0과 1로 이루어진 격자에서 같은 왼쪽 아래 꼭짓점을 공유하는 두 사각형(더 넓은 아래쪽, 더 높은 위쪽)으로 만들어지는 L자 모양 중 모든 칸이 1인 최대 넓이를 구합니다.
문제
n x m 크기의 격자 도화지에 0과 1로 이루어진 그림이 있다. 값이 1인 칸들만 사용해 L자 모양을 만들려고 한다.
이 문제에서 L자 모양은 같은 왼쪽 아래 꼭짓점을 공유하는 두 축에 평행한 직사각형의 합집합이다. 아래쪽 직사각형의 너비는 위쪽 직사각형의 너비보다 커야 하고, 위쪽 직사각형의 높이는 아래쪽 직사각형의 높이보다 커야 한다. L자 모양은 회전하거나 대칭하지 않으며, 단순한 직사각형은 L자 모양으로 보지 않는다.
그림 안에서 만들 수 있는 L자 모양 중 넓이가 가장 큰 것을 찾아 그 넓이를 출력하라. 입력에는 적어도 하나의 L자 모양이 존재한다.
입력
첫째 줄에 두 정수 n, m이 주어진다. 다음 n개의 줄에는 길이가 m인 문자열이 주어진다. 각 문자는 0 또는 1이다.
출력
첫째 줄에 만들 수 있는 L자 모양의 최대 넓이를 출력한다.
제한
- 1 <= n, m <= 150