AcWing 4405. 统计子矩阵
原题链接
中等
作者:
kooo.
,
2024-03-30 23:10:54
,
所有人可见
,
阅读 2
#include<iostream>
#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
#define ll long long
const int N=600;
ll a[N][N],b[N][N];
ll n,m;
ll k;
int main()
{
ll ans=0;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
b[i][j]=a[i][j];
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
for(int i=1;i<=m;i++)
{
for(int j=i;j<=m;j++)
{
for(int s=1,t=1;t<=n;t++)
{
while(s<=t&&(a[t][j]-a[s-1][j]-a[t][i-1]+a[s-1][i-1])>k)s++;
if(s<=t)ans+=t-s+1;
}
}
}
cout<<ans<<endl;
return 0;
}