COCI 2014/2015 contest6 5- 아주 멋진 사각형 (NEO) > 문제은행 : 정보올림피아드&알고리즘




2829 : 아주 멋진 사각형 (NEO)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
3 회   
시도횟수
41 회   

문제

R행 S열 격자가 있고 격자의 각 칸에는 -1,000,000 이상 1,000,000 이하의 정수가 쓰여 있다.

 

 

 

이 격자에서, 일부 칸을 선택하여 사각형을 만들 수 있다. 사각형들 중 다음 조건을 만족하면 ‘멋진 사각형’이다.

 

- 왼쪽 위의 칸과 오른쪽 아래 칸을 파란색으로, 왼쪽 아래 칸과 오른쪽 위의 칸을 빨간색으로 칠한다.
- 이때, 빨간 칸에 있는 수의 합보다 파란 칸에 있는 수의 합이 더 작거나 같으면 ‘멋진 사각형’이다.

 

한편, 사각형들 중 다음 조건을 만족하면 ‘아주 멋진 사각형’이라고 부르자.

 

- 선택한 범위의 부분 사각형 들에서 '멋진 사각형'이 두 개 이상 발견되면 '아주 멋진 사각형'이다.

 

격자에 들어있는 수가 주어질 때 가장 큰 크기의 ‘아주 멋진 사각형’을 구하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 격자의 크기 R, S가 주어진다. (2 ≤ R ≤ S ≤ 1,000) 두 번째 줄부터 R개의 줄에는 각 칸에 들어있는 수가 주어진다.

출력형식

가장 큰 ‘아주 멋진 사각형’의 크기(격자의 수)를 출력한다. 만약 주어진 격자에 '아주 멋진 사각형'이 없다면 0을 출력한다.

입력 예

3 3
1 4 10
5 2 6
11 1 3

출력 예

9

입력 예

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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP