問題描述

給定一個(gè)?N×M?的矩陣?A, 請你統(tǒng)計(jì)有多少個(gè)子矩陣 (最小1×1, 最大N×M)?滿足子矩陣中所有數(shù)的和不超過給定的整數(shù)?K??

輸入格式

第一行包含三個(gè)整數(shù)?$,M$?和?K.

之后?N?行每行包含?M?個(gè)整數(shù), 代表矩陣?A.

輸出格式

一個(gè)整數(shù)代表答案。

樣例輸入

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;

}