请求加强数据
查看原帖
请求加强数据
928879
stripe_python楼主2024/8/12 14:53

rt,O(n4)O(n^4) 过了。

#include <bits/stdc++.h>
#define N 405
using namespace std;

int n, m;
long long a[N][N], pre[N][N];
inline long long query(int x1, int y1, int x2, int y2) {
	return pre[x2][y2] - pre[x1 - 1][y2] - pre[x2][y1 - 1] + pre[x1 - 1][y1 - 1];
}

void _main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> a[i][j];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			pre[i][j] = a[i][j] + pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1];
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = i; k <= n; k++) {
				for (int t = j; t <= m; t++) {
					if (query(i, j, k, t) >= 0) {
						res = max(res, (k - i + 1) * (t - j + 1));
					}
				}
			}
		}
	}
	cout << res;
} signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr), cerr.tie(nullptr);

#ifndef SPN_LOCAL
#ifndef ONLINE_JUDGE
	freopen("rec.in", "r", stdin), freopen("rec.out", "w", stdout);
#endif
#endif

	int t = 1;
//	cin >> t;
	while (t--) _main();
	return 0;
}

2024/8/12 14:53
加载中...