AcWing 4405. 统计子矩阵
原题链接
中等
作者:
a_little
,
2024-04-04 18:41:10
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n,m;
int k;
int a[N][N];
int s[N][N];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[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]+a[i][j];
int cnt=0;
for(int x1=1;x1<=n;x1++){
for(int y1=1;y1<=m;y1++){
for(int x2=1;x2<=n;x2++){
for(int y2=1;y2<=m;y2++){
if(x2>=x1&&y2>=y1){
int sum=s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];
if(sum<=k) cnt++;
}
}
}
}
}
cout<<cnt;
return 0;
}