第十三届蓝桥杯 C++ B组 统计子矩阵

 

 

 

//我们可以看成一维前缀和
//每一列看成一个前缀和 然后 从上往下枚举行 
//根据单调性 可以使用 双指针算法
#include
#include
using namespace std;

const int N=510;
typedef long long LL;

int s[N][N];
int n,m,k;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&s[i][j]);
            s[i][j]+=s[i-1][j];//每一个元素都是这一列之前的所有元素和
        }
    
    LL res=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+=s[j][r]-s[i-1][r];//这一段和等于 s[j][r]-s[i-1][r]
                while(sum>k)
                {
                    sum-=s[j][l]-s[i-1][l];
                    l++;
                }
                res+=r-l+1;
            }
            
    printf("%lld\n",res);
    return 0;
}