시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 1 | 1 | 50.000% |
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:
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.
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 a single integer T, representing the maximum total luckiness that his design could produce.
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
24
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
-20