模拟赛
作者:
RecSys
,
2021-04-11 15:36:50
,
所有人可见
,
阅读 256
前缀和二维
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 505;
int n, m, q;
int s[N][N];
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d", &s[i][j]);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
int ans=0;
//printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
for(int k=1;k<=n;k++)
{
for(int l=1;l<=m;l++)
{
int x1=i,y1=j,x2=k,y2=l;
int temp=s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
ans=max(ans,temp);
}
}
}
}
cout<<ans;
return 0;
}