## APIO '09 P1 - Digging for Oil

View as PDF

Points: 20 (partial)
Time limit: 0.75s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 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 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 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 , the AoE cartel can take over plots with a combined estimated reserve of 100 units, whereas if 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 format

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

#### Output format

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 and and that at least three disjoint blocks are available. In 30% of the inputs, . In all inputs, . The estimated oil reserve for each plot is always non-negative and never exceeds .

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

208