APIO 2009 Contest, 1- 기름파기 > 문제은행 : 정보올림피아드&알고리즘




2425 : 기름파기

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
24 회   
시도횟수
83 회   

문제

정올 정부는 원유가 많이 묻혀 있는 정올 주의 땅을, 유전개발을 할 수 있는 개인사업자들에게 경매로 팔도록 결정하였다. 경매 처리할 전체 땅은 MⅹN 직사각형 격자 형태의 작은 구역으로 분할되었다.

정올 정부의 지질측정국은 정올 주 각 구역에 대한 원유 함유량 추정치 자료를 가지고 있다. 이 자료는 MⅹN 격자에 음이 아닌 정수로 작은 구역 별로 원유 함유량 추정치가 주어진다.

 

독점의 방지를 위하여, 정부는 어떤 계약자도 오직 하나의 KⅹK 규격의 정사각형 모양의 연속된 작은 구역들만 응찰 할 수 있도록 규정하였다. 3개의 사업자로 구성된 AOE(association of energy) 기름협회는 가능한 가장 많은 양의 원유 확보를 위하여 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 구역의 원유 함유량 추정치가 음이 아닌 정수로 주어 진다. M, N≤1,500 이고, K≤M 이고 K≤N이다. 

 

최소 세 개의 겹치지 않는 K * K 구역이 존재한다. 각 구역의 원유 함유량의 추정치는 모두 음수가 아닌 정수이고, 500 보다 작다.


출력형식

첫 줄에 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


경기도 안양시 동안구 평촌대로 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