AT_abc311_g [ABC311G] One More Grid Task

题目描述

有一个 $N \times M$ 的网格，在第 $i$ 行第 $j$ 列的格子 $(i,j)$ 上写有一个非负整数 $A_{i,j}$。
你可以从这个网格中选择一个矩形区域，记为 $R$。
具体来说，矩形区域的选择方式如下：

• 选择满足 $1 \leq l_x \leq r_x \leq N,\ 1 \leq l_y \leq r_y \leq M$ 的整数 $l_x, r_x, l_y, r_y$。
• 此时，只有当整数 $i, j$ 满足 $l_x \leq i \leq r_x$ 且 $l_y \leq j \leq r_y$ 时，格子 $(i,j)$ 才包含在 $R$ 中。

请通过恰当地选择 $R$，求出 $f(R) =$（$R$ 内所有格子中的整数之和）$\times$（$R$ 内所有格子中的整数的最小值）能够取得的最大值。

输入格式

输入按以下格式从标准输入读入。

$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

输入 #1

3 3
5 4 3
4 3 2
3 2 1

输出 #1

48

输入输出样例 #2

输入 #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

输入 #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

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N, M \leq 300$
• $1 \leq A_{i,j} \leq 300$

样例解释 1

选择左上角为格子 $(1,1)$，右下角为格子 $(2,2)$ 的矩形区域时，$f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48$，这是可以取得的最大值。

由 ChatGPT 4.1 翻译