考虑一维怎么做。
因为 \(a_i \ge 1\),所以保持最小值不变的前提下,区间左右端点扩展是更优的。我们使用单调栈求出左边第一个比 \(a_i\) 大的数 \(a_{l_i}\),以及右边第一个比 \(a_i\) 大的数 \(a_{r_i}\),答案即为 \(\max\limits_{i = 1}^n a_i \times (\sum\limits_{j = l_i + 1}^{r_i - 1} a_j)\)。
二维的情况,我们枚举矩形的上下边界 \([x, y]\),令 \(b_i = \min\limits_{j = x}^y a_{j, i}\),就转化成了一维的情况。时间复杂度 \(O(n^3)\)。
code
// Problem: G - One More Grid Task
// Contest: AtCoder - Toyota Programming Contest 2023#4(AtCoder Beginner Contest 311)
// URL: https://atcoder.jp/contests/abc311/tasks/abc311_g
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 310;
int n, m, a[maxn][maxn], b[maxn], stk[maxn], top, L[maxn], R[maxn], c[maxn][maxn];
inline int qsum(int xl, int xr, int yl, int yr) {
return c[xl - 1][yl - 1] + c[xr][yr] - c[xl - 1][yr] - c[xr][yl - 1];
}
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i][j];
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i) {
for (int k = 1; k <= m; ++k) {
b[k] = a[i][k];
}
for (int j = i; j <= n; ++j) {
for (int k = 1; k <= m; ++k) {
b[k] = min(b[k], a[j][k]);
}
top = 0;
for (int k = 1; k <= m; ++k) {
while (top && b[stk[top]] > b[k]) {
--top;
}
L[k] = (top ? stk[top] + 1 : 1);
stk[++top] = k;
}
top = 0;
for (int k = m; k; --k) {
while (top && b[stk[top]] >= b[k]) {
--top;
}
R[k] = (top ? stk[top] - 1 : m);
stk[++top] = k;
}
for (int k = 1; k <= m; ++k) {
ans = max(ans, 1LL * b[k] * qsum(i, j, L[k], R[k]));
}
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Beginner AtCoder Contest More Gridbeginner atcoder contest more atcoder 311g more grid contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334