← 返回题目列表

AtCoder · abc311_g

G. 又一项网格任务

中文机器翻译题面 查看原题

分数: 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