Informatica Online Judge

  기름파기 III [0338 / 0152]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 25   Total Tried : 151


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

시루세리 정부는 원유가 많이 묻혀 있는 나바루 주의 땅을, 유전개발을 할 수 있는 개인사업자 들에게 경매로 팔도록 결정하였다. 경매 처리할 전체 땅은 MⅹN 직사각형 격자 형태의 작은 구 역으로 분할되었다.
시루세리 정부의 지질측정국은 나바루 주 각 구역에 대한 원유 함유량 추정치 자료를 가지고 있다. 이 자료는 MⅹN 격자에 음이 아닌 정수로 작은 구역 별로 원유 함유량 추정치가 주어진다.
독점의 방지를 위하여, 정부는 어떤 계약자도 오직 하나의 KⅹK 규격의 정사각형 모양의 연속 된 작은 구역들만 응찰 할 수 있도록 규정하였다.
3개의 사업자로 구성된 AoE 기름협회는 가능한 가장 많은 양의 원유 확보를 위하여 3개의 위 에 설명된 규격의 구역을 겹치지 않게 선택하려고 한다.
추정된 원유 함유량이 다음과 같이 주어졌다고 하자:

1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

만일 K=2 라면, AoE 협
회는 구역의 선택을 통하여 총합이 100 단위의 추정 함유량의 확보가 가 능하며, K=3으로 주어질 경우 총합 208 단위의 추정 함유량의 확보가 가능하다.
AoE는 당신을 고용하여, 그들이 차지할 수 있는 최대한의 추정 원유 함유량을 알아내는 프로그 램을 작성하고자 한다.

Input

첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개 수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄 에는 각각 한 행에 해당하는 N 구역의 원유 함유량 추정치가 음이 아닌 정수로 주어 진다.
K ≤ M 또한 K ≤ N이고 최소 세 개의 겹치지 않는 KⅹK 구역이 존재한다. 각 구역의 원유 함유 량의 추정치는 모두 음수가 아닌 정수이고, 500 보다 작다.
(단, M ≤ 1500 , N ≤ 1500 )

Output

첫 줄에 AoE 기름 협회가 차지할 수 있는 최대 추정 원유 함유량을 출력한다.

IO Example

입력
9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9

출력
208

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