Checkerboard Cut

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

You found a grid with N rows and M columns, and each cell of the grid has some positive integer value v_{ij}. You are allowed to keep some subset of the cells of the grid as follows:

  • First, you must make some number of horizontal or vertical cuts along the grid lines. This cuts the grid into several rectangular regions that form a grid pattern. You must make at least one cut, but it is allowed to make only horizontal or only vertical cuts.
  • Next, you colour this new grid with two colours in a checkerboard pattern, where any two adjacent rectangular regions have a different colour.
  • Finally, you are allowed to keep all the grid cells that have the same colour.

You want to maximize the total value of all the cells you keep. Calculate this maximum possible sum.


For all test cases, at least one of N or M is greater than 1 and 1 \le v_{ij} \le 10^9 for all grid cells.

Subtask 1 [10%]

1 \le N,M \le 10

Subtask 2 [10%]

1 \le N \le 10

1 \le M \le 300

Subtask 3 [30%]

1 \le N,M \le 30

Subtask 4 [25%]

1 \le N,M \le 100

Subtask 5 [25%]

1 \le N,M \le 300

Input Specification

The first line of input contains two space-separated integers: N and M. The next N lines of input contain M space-separated integers, describing a row of the grid. The jth number on the ith of these lines is the value v_{ij}.

Output Specification

Output one number: the maximum possible total value of all cells you keep.

Sample Input 1

1 4
6 2 9 8

Sample Output 1


Explanation for Sample Output 1

By making two vertical cuts, it is possible to keep all values except for the 2.

Sample Input 2

3 4
9 1 7 8
2 8 1 1
7 3 5 6

Sample Output 2


Explanation for Sample Output 2

Make two horizontal cuts and two vertical cuts as shown below:

You can keep all the values in black cells, giving a total value of 50.


There are no comments at the moment.