Tasks:
 
Task DescriptionDiscussion (0)
Task :: APIO - Oil
The Government of Siruseri has decided to auction o land in its oil-rich Navalur province to private contractors to set up oil wells. The entire area that is being auctioned o has been divided up into an M *N rectangular grid of smaller plots.

The Geological Survey of Siruseri has data on the estimated oil reserves in Navalur. This information is published as an M*N grid of non-negative integers, giving the estimated reserves in each of the plots.

In order to prevent a monopoly, the government has ruled that any con-tractor may bid for only one K* K square block of contiguous plots.

The AoE oil cartel consists of a group of 3 colluding contractors who would like to choose 3 disjoint blocks so as to maximize their total yield.Suppose that the estimated oil reserves are as described below:


If K = 2 , the AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if K = 3 they can take over plots with a combined estimated reserve of 208 units.AoE has hired you to write a program to help them identify the maximum estimated oil reserves that they can take over.

INPUT:
The first line of the input contains three integers M, N and K, where M and N are the number of rows and columns in the rectangular grid of plots and K is the size of the square block for which bids can be made. The next M lines contain N non-negative integers|each line describes the estimated oil reserves for one row of plots.

OUTPUT:
A single line with a single integer indicating the maximum estimated oil reserves that can be taken over by the AoE cartel.

Test Data
You may assume that K <= M and K <= N and that at least three disjoint K*K blocks are available. In 30% of the inputs, M,N <= 12. In all inputs, M,N <= 1500. The estimated oil reserve for each plot is always non-negative and never exceeds 500.

Input
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

Output
208
Submit Solution
:
:
Available Languages
Task info
Name:APIO - Oil
Time:0.75 sec.
Memory:128 MB
#Tests:17
AddedBy: dario-dsa
Source:APIO 2009
Task Ratings
Difficulty:

3.3 (8 votes)
Quality:

2.7 (7 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
makanbeling 1.652 s.
sokokaleb 1.728 s.
harta01 2.347 s.
vlad107 2.844 s.
phungha 2.873 s.
oa12gb 2.957 s.
1010011010 3.124 s.
dayatbflash 3.246 s.
ptrrsn_1 3.259 s.
momohuang 3.335 s.
Solved By