grid with m rows and n columns, and a number cap.
A block is any non-empty rectangular part of the table: a run of consecutive rows crossed with a run of consecutive columns. A block is good when:
- all of its values are at most cap;
- in each of its rows the values never increase from left to right (neighbours may be equal).
Return the number of good blocks. Blocks are told apart by their position in the table, even when their contents match.grid=[[5, 2, 2], [3, 3, 1]], cap=3 → 12
Values at most 3 with rows that never increase left to right: five single cells (all but the 5), the row pieces [2, 2], [3, 3], [3, 1] and [3, 3, 1], two height-2 columns [[2], [3]] and [[2], [1]], and the 2×2 block [[2, 2], [3, 1]]. Twelve in total.
grid=[[1, 2], [1, 2]], cap=5 → 6
The rows [1, 2] increase, so only blocks of width 1 work: the four cells and the two height-2 columns.
grid=[[7]], cap=6 → 0
The only cell is above cap.
m, n ≤ 1000grid[i][j], cap ≤ 10⁹grid=[[5, 2, 2], [3, 3, 1]], cap=3
12
Run checks the first 3 tests in your browser. Submit checks all 107 tests on the server, hidden ones included.