Loading...
Loading...
Loading...
A table of integers has R rows and C columns. Count the rectangular blocks of cells, of any size, whose sum is exactly k. Blocks at different positions count separately.
Example
Input
2 3 3 1 2 1 -1 1 2
Output
6
Several blocks add up to 3.
Try the problem first. Open one hint at a time.
Fix a top row and a bottom row. Add the rows between them into one list of column totals.
Then count blocks of that list with sum k, using prefix sums and a Counter.
Write your Python code, run it on the examples and submit it to hidden tests.
Solve in the editor