#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
//数据结构在这里定义
const int N =1e3+10;
int a[N][N];//原数据
ll sum[N][N];//求和要ll
int n,m,k;
//求和函数和ans不开long long只能过70%
ll pre(int x, int y, int i, int j){
return sum[i][j] - sum[x-1][j] \
- sum[i][y-1] + sum[x-1][y-1];
}
void solve(){
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];
}
}
ll ans = 0;
for(int up = 1; up<=n;up++){
for(int down = up; down <=n;down++){
//上下确定了此时问题压缩为一维
//滑动窗口法
int left = 1,right=1;
for(;right<=m;right++){
//right添加元素
while(pre(up,left,down,right)>k && left <= right){
//总和不满足条件,收缩left
left++;
}
if(left<=right){
//合法区间
//计算sublen 这里是最长子区间大小
ans += right - left + 1;
}
}
}
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;//多组数据要cin
//cin >> t;
t = 1;
while(t--){
solve();
}
return 0;//必须加return 0
}
0 回复
0 转发
0 喜欢
4 阅读



