leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

3070.cpp (1160B)

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 };