前缀和+双指针优化（过100%）

解题思路:

注意事项:

参考代码:

import java.util.Scanner;

public class Main {
    static final int N = 505;
    static int[][] s = new int[N][N];
    static int n, m;
    static long res, k;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextLong();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                s[i][j] = sc.nextInt();
                if (i > 0) {
                    s[i][j] += s[i - 1][j]; // 预处理每一列前缀和
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                long sum = 0;
                int l = 0;
                for (int r = 0; r < m; r++) {
                    if (i > 0) {
                        sum += s[j][r] - s[i - 1][r];
                    } else {
                        sum += s[j][r];
                    }
                    while (sum > k) {
                        if (i > 0 && l >= 0) {
                            sum -= s[j][l] - s[i - 1][l];
                        } else if (l >= 0) {
                            sum -= s[j][l];
                        }
                        l++;
                    }
                    res += r - l + 1;
                }
            }
        }

        System.out.println(res);
    }
}