题目描述

二维前缀和+双指针。

双指针：我们是把大于k的排除，然后总区间 - 大于k区间 + 1

样例

import java.util.*;

public class Main{
    static final int N = 1010;
    static int[][] a = new int[N + 5][N + 5];
    static int[][] s = new int[N + 5][N + 5];
    static long res;

    static void init(int n, int m) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];//算[0,0]到[X1,Y1]
            }
        }
    }

    static int sumPrefix(int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];//算[X1,Y1]到[X2,Y2]
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int k = in.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = in.nextInt();
            }
        }
        init(n, m);

        /*
          l=x1 up=y1 r=x2 down=y2
          双指针的思想：up和down就是双指针

          一次执行：
          先把[1][]和[1][]定下来，第三个for定义列的循环，while循环让up递增，并且up<=down
          循环结束，此时down和r之间的个数就是符合子矩阵的个数(条件是判断大于k,最后相当于整个区间减去大于k的区别)
          down再++
        */
        for (int l = 1; l <= n; l ++)
            for (int r = l; r <= n; r ++)
                for (int up = 1, down = 1; down <= m; down ++) {
                    while (up <= down && sumPrefix(l, up, r, down) > k)
                        up ++;
                    res += Math.max(0, down - up + 1);
                }

        System.out.println(res);
    }
}