4405. 统计子矩阵
用前缀和与双指针可以优化掉这题,我们用前缀和存下每列的前缀和,再用双指针枚举每一行的每一列,
code
#include<bits/stdc++.h>
using namespace std;
int dp[510][510];
typedef long long ll;
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>dp[i][j];
dp[i][j]+=dp[i-1][j];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
for(int l=1,r=1,sum=0;r<=m;r++)
{
sum+=dp[j][r]-dp[i-1][r];
while(sum>k)
{
sum-=dp[j][l]-dp[i-1][l];//如果大于k就减掉l的这一列,让l往前
l++;
}
ans+=r-l+1;
}
}
}
cout<<ans<<endl;
}