分数: 575 点
问题陈述
有一个 N \times M 网格,其中正方形位于 i从顶部数第行和 j左起第 列有一个非负整数
上面写着 A_{i,j} 。
让我们选择一个矩形区域 R.
正式地,区域选择如下。
- 选择整数 l_x, r_x, l_y, r_y 这样 1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M.
- 然后,正方形 (i,j) 位于 R 当且仅当 l_x \le i \le r_x 和 l_y \le j \le r_y.
找到最大可能值 f(R) = (写在方格上的整数之和 R) \times (写在正方形上的最小整数 R).
约束
- 所有输入值均为整数。
- 1 \le N,M \le 300
- 1 \le A_{i,j} \le 300
输入
输入由标准输入按以下格式给出:
N M
A_{1,1} A_{1,2} \dots A_{1,M}
A_{2,1} A_{2,2} \dots A_{2,M}
\vdots
A_{N,1} A_{N,2} \dots A_{N,M}
输出
将答案打印为整数。
示例输入 1
3 3 5 4 3 4 3 2 3 2 1
示例输出 1
48
选择左上角为正方形的矩形区域 (1, 1) 并且其右下角是正方形 (2, 2) 实现 f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48,这是最大可能值。
示例输入 2
4 5 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
示例输出 2
231
示例输入 3
6 6 1 300 300 300 300 300 300 1 300 300 300 300 300 300 1 300 300 300 300 300 300 1 300 300 300 300 300 300 1 300 300 300 300 300 300 1
示例输出 3
810000