算法竞赛2022年第十三届蓝桥杯C++ B组_统计子矩阵

// https://www.acwing.com/problem/content/submission/4408/

// 代码已经检测通过

#include<iostream>  

#include<algorithm>

 using namespace std;

typedef long long ll;

const int N = 503;

int n=3, m=4, k=10;

int a[N][N]={

{0,0, 0, 0, 0},

{0,1, 2, 3, 4},

{0,5, 6, 7, 8},

{0,9, 10, 11, 12}

};

int main(){

 

   // cin >> n >> m >> k;

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

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

           // cin >> a[i][j];

            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];

        }

    }

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

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

            cout <<  a[i][j]<<"   ";            

        }

cout << endl;

    }

    ll ans = 0;

    for(int i=1; i<=m; i++){

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

            for(int s = 1, t = 1; t <= n; t ++ ){

// a[t][j] - a[s - 1][j]    --> j 列  t-(s-1)行

// a[t][i - 1] - a[s - 1][i - 1]    i-1 列  t-(s-1)行

//  j-(i-1) 列  t-(s-1)行,        左上角(s,i),  右下角 (t,j) 确定矩阵的元素之和

                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; // 最大行为t行(包含i列到j列)的矩阵个数

            }

        }

    }

    cout << ans << '\n';

}