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

#2425 upload 96 done 28 how_to_reg 25

기름파기 timer 1s memory 256MB

#2425

기름파기 1s 256MB