One More Grid Task

题目描述

有一个 $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$。 那么，当且仅当 $l_x \le i \le r_x$ 且 $l_y \le j \le r_y$ 时，方格 $(i,j)$ 属于 $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}$

输出格式

输出一个整数，表示答案。

3 3
5 4 3
4 3 2
3 2 1

48

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4

231

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

810000

提示

所有输入值均为整数。 $1 \le N,M \le 300$ $1 \le A_{i,j} \le 300$选择左上角为方格 $(1, 1)$、右下角为方格 $(2, 2)$ 的矩形区域可得到 $f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48$，这是能取得的最大值。

标签: AtCoder|abc311G

来源

AtCoder|abc311G