PKU 1050. To the Max

제일 크게

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 20504	Accepted: 10588

설명

부호에 상관없는 2차원 평면상의 정수집합체를 주고, 그 안에서 전체 크기 안에 들어가는 1*1 또는 그보다 조금 더 큰 직사각형 모양의 부분집합체를 잡습니다. 직사각형의 합은 직사각형 안에 들어가는 모든 원소의 합을 의미합니다. 가장 합이 큰 직사각형이라는 것은, 직사각형으로 이루어지는 모든 부분집합체들 중 원소들의 합이 가장 큰 직사각형을 의미합니다.  
예를 들어 다음 집합체에서 가장 합이 큰 직사각형은

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 
왼쪽 아래 부분에 있고

9 2 
-4 1 
-1 8 
그 합은 15입니다. 

입력

입력할 때 정수집합체는 N * N 의 형태를 갖습니다. 입력은 첫 줄에 하나의 양정수 N으로 시작하는데, 이 N 은 정사각형 형태의 정수집합체의 한 변의 크기를 나타냅니다. 그러므로 이 뒤에는 N^2 개의 정수들이 나오는데, 각각 공백 또는 줄바꿈 등으로 분리해서 입력합니다. 이 N^2 개의 정수들은 행렬로 나타내었을 때 1행부터, 같은 행에 있는 숫자들은 1열에 있는 수부터 기재합니다. N 은 최대 100 까지의 값까지 허용됩니다. 모든 정수들은 폐구간 [-127,127] 안의 숫자들로 이루어져야 합니다.

출력

가장 합이 큰 직사각형의 합 을 출력합니다.

입력 예시

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1

8  0 -2

출력 예시

15

Source

Greater New York 2001

p.s: row-major order 라는게 행 우선 순서 라고 할 수 있을것 같기도 한데 완전히 처음 들어보는 정렬방식이군요 전.