leetcode

0 static const auto _ = []() {

1 ios_base::sync_with_stdio(false);

2 cin.tie(NULL);

3 cout.tie(NULL);

4 return 0;

5 }();

6

7 class Solution {

8 public:

9 int countSubmatrices(vector<vector<int>> &grid, int k) const {

10 int n = size(grid), m = size(grid[0]), res = grid[0][0] <= k;

11

12 for (int i = 1, acc = grid[0][0]; i < n; i++) {

13 grid[i][0] = acc += grid[i][0];

14 if (grid[i][0] <= k)

15 res++;

16 else {

17 n = i;

18 break;

19 }

20 }

21

22 for (int j = 1, acc = grid[0][0]; j < m; j++) {

23 grid[0][j] = acc += grid[0][j];

24 if (grid[0][j] <= k)

25 res++;

26 else {

27 m = j;

28 break;

29 }

30 }

31

32 for (int i = 1; i < n; i++) {

33 for (int j = 1; j < m; j++) {

34 grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];

35 if (grid[i][j] <= k)

36 res++;

37 else {

38 m = j;

39 break;

40 }

41 }

42 }

43

44 return res;

45 }

46 };