Indian Computing Olympiad

Computing Prefix Sums→Oil (APIO 2009)

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×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 contractor 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:

      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 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.

Solution

---