洛谷 P1719. 最大加权矩形
原题链接
中等
作者:
我是java同学
,
2024-02-01 17:09:29
,
所有人可见
,
阅读 35
#include <bits/stdc++.h>
using namespace std;
const int N = 125;
int n;
int s[N][N];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ) {
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
}
int res = -1e9;
for (int x2 = 1; x2 <= n; x2 ++ )
for (int y2 = 1; y2 <= n; y2 ++ )
for (int x1 = x2; x1 <= n; x1 ++ )
for (int y1 = y2; y1 <= n; y1 ++ ) {
res = max(res, s[x1][y1] - s[x1][y2 - 1] - s[x2 - 1][y1] + s[x2 - 1][y2 - 1]);
}
cout << res << endl;
return 0;
}