【统计子矩阵——部分前缀和+双指针】

题目

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
int s[N][N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);int n, m, k;cin >> n >> m >> k;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++){cin >> s[i][j];s[i][j] += s[i-1][j];}ll ans =  0;for(int i = 1; i <= n; i++){for(int j = i; j <= n; j++){for(int l = 1, r = 1, sum = 0; r <= m; r++){sum += s[j][r] - s[i-1][r];while(sum > k){sum -= s[j][l] - s[i-1][l];l++;}ans += r - l + 1;}}}cout << ans;
}