526互联

前缀和

发布时间 2023-04-03 22:08:20作者: lyc2002

[acwing]4405 .统计子矩阵

#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 510;

int n, m, k;
int s[N][N];
LL res;

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &s[i][j]);
            s[i][j] += s[i - 1][j];
        }
        
    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++;
                }
                res += r - l + 1;
            }
        
    printf("%lld", res);
    
    return 0;
}