National Olympiad in Informatics, China, 2013

Day 2, Problem 2 - Calligrapher

Little E really likes calligraphy. He heard that NOI2013 has started, and would like to give a calligraphic design of "NOI" to everyone.

Little E has one sheet of magical paper. The paper can be represented as a two-dimensional grid with n rows and m columns. We consider the coordinates of the bottom-left corner to be (1, 1) and the coordinates of the top-right corner to be (m, n). Each cell of the grid contains an integer "luckiness" value. Writing on a cell can increase everyone's luckiness. The overall luckiness just happens to be the sum of the luckiness values across all cells that have been written on. Now, you need to write the three letters 'N', 'O', and 'I' onto the paper.

The three calligraphic letters are defined as follows:

1. The 'N' is made up of some number (≥ 3) of rectangles which are parallel to the grid's axes. Let K be the number of rectangles (numbered from 1 to K), then the i-th rectangle's bottom-left corner will have coordinates (L_i, B_i), and its top-right corner will have coordinates (R_i, T_i). These values will satisfy:
   1. L_i ≤ R_i,  B_i ≤ T_i;
   2. For all 1 < i ≤ K, it will hold true that L_i = R_i−1 + 1;
   3. For all 3 ≤ i < K, it will hold true that B_i−1 − 1 ≤ T_i ≤ T_i−1,  B_i ≤ B_i−1;
   4. B₂ > B₁,  T₂ = T₁,  B_K−1 = B_K,  T_K−1 < T_K.
2. The 'O' is made up of a bigger rectangle A, with a smaller rectangle B carved out of it. The two rectangles both have sides parallel to the grid's axes. Let (u, v) represent the coordinates of the bottom-left corner of rectangle A, and W and H represent its width and height respectively. Then, the smaller rectangle B will have bottom-left corner at (u + 1, v + 1), a width of W − 2, and a height of H − 2. These values will satisfy:
   1. W ≥ 3,  H ≥ 3;
   2. u > R_K + 1.
3. The 'I' is made up of 3 rectangles with sides parallel to the grid's axes, numbered 1, 2, and 3 from bottom to top. Let (P_i, Q_i) represent the coordinates rectangle i's bottom-left corner, and (G_i, H_i) represent the coordinates of its top-right corner. These values will satisfy:
   1. P_i ≤ G_i,  Q_i ≤ H_i;
   2. P₁ = P₃ > u + W,  G₁ = G₃;
   3. Q₁ = H₁ = Q₂ − 1,   H₂ + 1 = Q₃ = H₃;
   4. P₁ < P₂ ≤ G₂ < G₁;

The following depicts an example of a valid calligraphic design of the letters 'N', 'O', and 'I'.

Also, shapes drawn in the design must not extend beyond the boundaries of the grid. Little E would like to determine the maximum possible luckiness that his design could produce.

Input Format

The first line of input will contain two positive integers n and m, respectively representing the number of rows and columns in the grid.
The next n lines will each contain m integers. The j-th integer on line i + 1 of the input represents the luckiness value of the grid cell at (j, n − i + 1).

Output Format

Output a single integer T, representing the maximum total luckiness that his design could produce.

Sample Input 1

3 13
1 1 -1 -1 1 -1 1 1 1 -1 1 1 1
1 -1 1 -1 1 -1 1 -1 1 -1 -1 1 -1
1 -1 -1 1 1 -1 1 1 1 -1 1 1 1

Sample Output 1

24

Explanation for Sample 1

Sample Input 2

3 13
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

Sample Output 2

-20

Explanation for Sample 2

The following is one optimal design. There also exists other optimal designs.

Constraints

All test cases satisfy n ≥ 3 and m ≥ 12.

All Submissions
Best Solutions

Point Value: 30 (partial)
Time Limit: 2.00s
Memory Limit: 512M
Added: May 18, 2015

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)