103116: [Atcoder]ABC311 G - One More Grid Task
Description
Score : $575$ points
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
Input
题意翻译
给你一个 $n\times m$ 的矩阵 $a$，求： $$ \max_{1\leq l_1\leq r_1\leq n,1\leq l_2\leq r_2\leq m} (\sum_{l_1\leq i\leq r_1,l_2\leq j\leq r_2}a_{i,j} \times\min_{l_1\leq i\leq r_1,l_2\leq j\leq r_2}a_{i,j}) $$Output
分数：$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