APIO '09 P1 - Digging for Oil - Olympiads Online Judge

APIO '09 P1 - Digging for Oil

Points: 20 (partial)

Time limit: 0.75s

Memory limit: 128M

Problem type

The Government of Siruseri has decided to auction off land in its oil-rich Navalur province to private contractors to set up oil wells. The entire area that is being auctioned off has been divided up into an $M \times N$ ~M \times 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 \times N$ ~M \times 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 contractor may bid for only one $K \times K$ ~K \times 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:

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

If $K = 2$ ~K = 2~, the AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if $K = 3$ ~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 Specification

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

Output Specification

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 \le M$ ~K \le M~ and $K \le N$ ~K \le N~ and that at least three disjoint $K \times K$ ~K \times K~ blocks are available. In 30% of the inputs, $M, N \le 12$ ~M, N \le 12~. In all inputs, $M, N \le 1500$ ~M, N \le 1500~. The estimated oil reserve for each plot is always non-negative and never exceeds $500$ ~500~.

Sample 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

Sample Output

Comments

There are no comments at the moment.