기름 파기

프로그램 명: oil

제한시간: 1.5 초

시루세리 정부는 원유가 많이 묻혀 있는 나바루 주의 땅을, 유전개발을 할 수 있는 개인사업자 들에게 경매로 팔도록 결정하였다. 경매 처리할 전체 땅은 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는 당신을 고용하여, 그들이 차지할 수 있는 최대한의 추정 원유 함유량을 알아내는 프로그램을 작성하고자 한다.

입력

첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다.
다음 M개의 줄에는 각각 한 행에 해당하는 N 구역의 원유 함유량 추정치가 음이 아닌 정수로 주어 진다.

출력

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

입출력 예

입력

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

테스트 데이터

K ≤ M 또한 K ≤ N이고 최소 세 개의 겹치지 않는 KⅹK 구역이 존재한다. 입력들 중 30%는 M, N ≤ 12 이고, 나머지 모든 입력은 M, N ≤ 1500 이다. 각 구역의 원유 함유 량의 추정치는 모두 음수가 아닌 정수이고, 500 보다 작다.

출처: 아시아-태평양 정보 올림피아드 2009

[질/답] [제출 현황] [푼 후(6)]

[ 채 점 ] [홈으로] [뒤 로]