问题描述

给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小1×1, 最大N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?

输入格式

第一行包含三个整数 $,M$ 和 K.

之后 N 行每行包含 M 个整数, 代表矩阵 A.

输出格式

一个整数代表答案。

样例输入

3 4 10

1 2 3 4

5 6 7 8 

9 10 11 12

样例输出

19

#include<iostream>

#include<set>

#include<sstream>

#include<string>

#include<algorithm>

using namespace std;

long long n,m,k,cnt;

int a[510][510];

int getsum(int x1,int y1,int x2,int y2){

int sum=0;

for(int i=x1;i<=x2;i++){

for(int j=y1;j<=y2;j++){

sum+=a[i][j];

}

}

return sum;

}

int main()

{

cin>>n>>m>>k;

for(int i=0;i<n;i++){

for(int j=0;j<m;j++){

cin>>a[i][j];

}

}

for(int i=0;i<n;i++){

        for(int j=0;j<m;j++){

            for(int x=i;x<n;x++){

                for(int y=j;y<m;y++){

                    if(getsum(i,j,x,y)<=k)cnt++;

                }

            }

        }

    }

cout<<cnt;

return 0;

}