All submissions for this problem are available.
Given a matrix sized m x n, we define an O-region as a non-empty sub-block with another non-empty sub-block inside removed, such that the removed sub-block has no common boundaries with the outside. That is, the leftmost column of the removed sub-block must be different from the leftmost column of the outer sub-block, and similarly the rightmost columns, topmost rows, and bottommost rows are different. The removal of the inner sub-block leaves a region which looks like the letter O.
The value of an O-region is the sum of all numbers in the outer sub-block but not in the removed one. Your task is finding the maximal value of all O-regions appearing in the given matrix.
There are several test cases (fifteen at most), each formed as follows:
- The first line contains two positive integers m, n (3 ≤ m, n ≤ 77).
- m lines follow, each containing n integers (each having an absolute value of 105 at most) describing the matrix.
The input is ended with m = n = 0.
For each test case, output on a line an integer which is the respective maximal value found.
Input: 3 3 1 1 1 1 3 -1 1 1 1 4 5 1 -2 3 -4 5 -5 4 -3 2 -1 1 -3 5 -7 9 -9 7 -5 3 -1 0 0 Output: 6 19
|Tags||anhdq, easy, march11|
|Time Limit:||1.98351 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.