Informatica Online Judge

  사각형의 합 [0834 / 0342]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 37   Total Tried : 236


The Champion of this Problem (C++) : gs17068 - 2ms / 794byte
My Best Submission (C++) : N/A

[]

Background

N*N 행렬이 있다. 행렬 안에 있는 수들은 한 자리의 양 또는 음의 정수이다. 행렬에서 최대값이 될 수 있는 부분 직사각형을 구하고, 이 때의 최대값을 출력하는 프로그램을 작성하여라.
예를 들어, 다음과 같은 행렬이 주어졌다고 하자.

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

위 행렬에서 다음 부분 직사각형이 최대값이 되는 직사각형이다.

9 2
-4 1
-1 8

그리고, 이 때의 합은 15이므로 답은 15가 된다.

Input

첫 줄에 행렬의 크기 N이 주어진다. (1 <= N <= 500)
둘째 줄부터 N개의 줄에 걸쳐 각 행의 숫자들이 공백으로 분리되어 주어진다.

Output

첫 줄에 주어진 행렬에서 만들 수 있는 부분 직사각형들 중의 그 합들의 최대값을 출력한다.

IO Example

입력 예
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2


출력 예
15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]