Score : $575$ points

问题描述

存在一个 $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)$ 可能的最大值，其中 $f(R) =$（区域内所有格子上整数之和）$\times$（区域内格子上最小的整数）。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is an $N \times M$ grid, where the square at the $i$-th row from the top and $j$-th column from the left has a non-negative integer $A_{i,j}$ written on it.
Let us choose a rectangular region $R$.
Formally, the region is chosen as follows.

• Choose integers $l_x, r_x, l_y, r_y$ such that $1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M$.
• Then, square $(i,j)$ is in $R$ if and only if $l_x \le i \le r_x$ and $l_y \le j \le r_y$.

Find the maximum possible value of $f(R) =$ (the sum of integers written on the squares in $R$) $\times$ (the smallest integer written on a square in $R$).

Constraints

• All input values are integers.
• $1 \le N,M \le 300$
• $1 \le A_{i,j} \le 300$

Input

The input is given from Standard Input in the following format:

$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}$

Output

Print the answer as an integer.

Sample Input 1

3 3
5 4 3
4 3 2
3 2 1

Sample Output 1

48

Choosing the rectangular region whose top-left corner is square $(1, 1)$ and whose bottom-right corner is square $(2, 2)$ achieves $f(R) = (5+4+4+3) \times \min(5,4,4,3) = 48$, which is the maximum possible value.

Sample Input 2

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

Sample Output 2

231

Sample Input 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

Sample Output 3

810000

update @ 2024/3/10 08:51:59