409959: GYM103870 D Penalty

Thomas is doing a contest! He is facing many different problems he wants to solve, for a chance to be able to game again. The contest itself is structured like a $$$n \times m$$$ grid, where each cell entry represents the points Thomas gets if he solves that particular problem. During the contest, Thomas will choose exactly one sub-rectangle of problems, and solve all of the problems inside it to earn those points. Thomas wants to make sure his points earned is as maximal as possible. However, there is one problem in this contest (let's call it problem E) that gives a negative amount of points. Help Thomas find the maximum number of points he can earn by solving one sub-rectangle of the problems! (Please note that Thomas cannot skip problems in the rectangle that he picked).

The first line contains two integers, $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 500)$$$ denoting the dimensions of the grid. It is guaranteed that the area of the grid is strictly greater than $$$1$$$.

The following $$$n$$$ lines contain $$$m$$$ integers each, the respective row of the grid. Each element in the grid will have an absolute value $$$\leq 100$$$.

There will be exactly one negative value in the entire grid.

One integer, denoting the maximum number of points Thomas can earn by solving one sub-rectangle.

3 3
5 5 5
5 -40 5
5 5 5

15

1 4
0 33 -1 66

98

For the first sample, no matter how you look at it, Thomas does not gain from solving the middle problem worth $$$-40$$$. So the maximum number of points he can earn is $$$15$$$ from either solving the top row, bottom row, rightmost column, or leftmost column.

In the second sample, Thomas can solve the entire grid, since the gains from the $$$33$$$ and $$$66$$$ outweigh the $$$-1$$$ in the middle.

—

Idea: 3366

Preparation: 3366

Occurrences: Novice 4, Intermediate 3