leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

3070.cpp (1160B)

      1 static const auto _ = []() {
      2     ios_base::sync_with_stdio(false);
      3     cin.tie(NULL);
      4     cout.tie(NULL);
      5     return 0;
      6 }();
      7 
      8 class Solution {
      9   public:
     10     int countSubmatrices(vector<vector<int>> &grid, int k) const {
     11         int n = size(grid), m = size(grid[0]), res = grid[0][0] <= k;
     12 
     13         for (int i = 1, acc = grid[0][0]; i < n; i++) {
     14             grid[i][0] = acc += grid[i][0];
     15             if (grid[i][0] <= k)
     16                 res++;
     17             else {
     18                 n = i;
     19                 break;
     20             }
     21         }
     22 
     23         for (int j = 1, acc = grid[0][0]; j < m; j++) {
     24             grid[0][j] = acc += grid[0][j];
     25             if (grid[0][j] <= k)
     26                 res++;
     27             else {
     28                 m = j;
     29                 break;
     30             }
     31         }
     32 
     33         for (int i = 1; i < n; i++) {
     34             for (int j = 1; j < m; j++) {
     35                 grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1];
     36                 if (grid[i][j] <= k)
     37                     res++;
     38                 else {
     39                     m = j;
     40                     break;
     41                 }
     42             }
     43         }
     44 
     45         return res;
     46     }
     47 };