AcWing 4405. 统计子矩阵
原题链接
中等
作者:
文氘
,
2024-04-11 13:51:47
,
所有人可见
,
阅读 1
#include<iostream>
using namespace std;
const int N=510;
int n,m,k;
int s[N][N];
long long ans;
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>s[i][j];
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
}
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++){
for(int a=1,b=1;b<=n;b++){
//固定右端b,当所有数的和超过了K时,a右移
while(a<=b&&s[b][j]-s[a-1][j]-s[b][i-1]+s[a-1][i-1]>k) a++;
//当所有数的和小于等于K时,满足答案的条件,a右边的所有位置都满足条件,所以直接计数
if(a<=b) ans+=b-a+1;
}
}
}
cout<<ans;
return 0;
}