P3625 [APIO2009] Oil Extraction Area

The Siruseri government has decided to auction off land in the oil-rich province of Navalur to private contractors for building oil wells. The land to be auctioned is a rectangular area divided into $M \times N$ blocks. The Siruseri Geological Survey has estimates of the oil reserves in Navalur. These are given as $M \times N$ positive integers, i.e., the estimated yield for each block. To avoid monopoly, the government stipulates that each contractor may lease only one square region consisting of $K \times K$ adjacent blocks. The AoE Oil Consortium consists of three contractors. They want to choose three pairwise non-overlapping $K \times K$ regions so that the total yield is maximized. For example, suppose the estimated yields are as follows: ``` 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$, the total yield the AoE company can get is $100$. - If $K = 3$, the total yield the AoE company can get is $208$. AoE hires you to write a program to compute the maximum possible sum of yields of the regions they can lease.

The first line contains three positive integers $M$, $N$, $K$, where $M$ and $N$ are the numbers of rows and columns of the rectangle, and $K$ is the side length (in blocks) of each contractor’s square region. The next $M$ lines each contain $N$ positive integers giving the estimated yield for each block in that row.

Output a single integer: the maximum possible total yield of the three leased regions.

It is guaranteed that $K \le M$ and $K \le N$, and that there exist at least three pairwise disjoint $K \times K$ square regions. For $30\%$ of the testdata, $M, N \le 12$. For all testdata, $M, N \le 1500$. The estimate for each block is a non-negative integer not exceeding $500$. Translated by ChatGPT 5