トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)
G
One More Grid Task
AtCoder
⌀ 2265
原题
← Ex→
翻译中…

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.

翻译中…

样例

Input #1
3 3
5 4 3
4 3 2
3 2 1
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.
Input #2
4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
Output #2
231
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
Output #3
810000
题目信息
题号
abc311_g
时间限制
3 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。