36 lines
948 B
C++
36 lines
948 B
C++
// lanqiao 2109 统计子矩阵(二维前缀和)
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
#define int long long
|
|
const int N = 5e2 + 10;
|
|
int n, m, k;
|
|
int a[N][N], sum[N][N];
|
|
// 暴力解法，枚举子矩阵，二维前缀和求矩阵和，时间复杂度 O(n^4)
|
|
signed main(){
|
|
cin >> n >> m >> k;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= m; j++){
|
|
cin >> a[i][j];
|
|
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
|
|
}
|
|
}
|
|
int ans = 0, res;
|
|
for(int i = 1; i <= n; i++){
|
|
for(int j = 1; j <= m; j++){
|
|
for(int i1 = i; i1 <= n; i1++){
|
|
for(int j1 = j; j1 <= m; j1++){
|
|
res = sum[i1][j1] - sum[i-1][j1] - sum[i1][j-1] + sum[i-1][j-1];
|
|
if(res <= k) ans++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
cout << ans << endl;
|
|
return 0;
|
|
}
|
|
/* samples -> 19
|
|
3 4 10
|
|
1 2 3 4
|
|
5 6 7 8
|
|
9 10 11 12
|
|
*/ |