문제
R행 S열 격자가 있고 격자의 각 칸에는 -1,000,000 이상 1,000,000 이하의 정수가 쓰여 있다.
이 격자에서, 일부 칸을 선택하여 사각형을 만들 수 있다. 사각형들 중 다음 조건을 만족하면 ‘멋진 사각형’이다.
- 왼쪽 위의 칸과 오른쪽 아래 칸을 파란색으로, 왼쪽 아래 칸과 오른쪽 위의 칸을 빨간색으로 칠한다. - 이때, 빨간 칸에 있는 수의 합보다 파란 칸에 있는 수의 합이 더 작거나 같으면 ‘멋진 사각형’이다.
한편, 사각형들 중 다음 조건을 만족하면 ‘아주 멋진 사각형’이라고 부르자.
- 선택한 범위의 부분 사각형 들에서 '멋진 사각형'이 두 개 이상 발견되면 '아주 멋진 사각형'이다.
격자에 들어있는 수가 주어질 때 가장 큰 크기의 ‘아주 멋진 사각형’을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 격자의 크기 R, S가 주어진다. (2 ≤ R ≤ S ≤ 1,000)
두 번째 줄부터 R개의 줄에는 각 칸에 들어있는 수가 주어진다.
출력
가장 큰 ‘아주 멋진 사각형’의 크기(격자의 수)를 출력한다. 만약 주어진 격자에 '아주 멋진 사각형'이 없다면 0을 출력한다.
예제 #1
3 3
1 4 10
5 2 6
11 1 3
9
예제 #2
5 6
1 1 4 0 3 3
4 4 9 7 11 13
-3 -1 4 2 8 11
1 5 9 5 9 10
4 8 10 5 8 8
15
출처
COCI 2014/2015 contest6 5
로그인해야 코드를 작성할 수 있어요.