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

// 代碼已經(jīng)檢測通過

#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(luò)列)的矩陣個數(shù)

? ? ? ? ? ? }

? ? ? ? }

? ? }

? ? cout << ans << '\n';

}

?