Matrix Sum
Time limit2sMemory limit256 MB
Count the submatrices of an N by M matrix whose element sum is at most x.
- Level
Medium7 of 10
- Topics
- Prefix sum, Two pointers, Binary search, Array
- Solved
- No attempts yet
Problem
You are given an N by M integer matrix A and an integer x. Among all submatrices of A, you want to count those whose element sum is at most x. For example, let N = M = 2, x = 5, and let A be as follows.
1 2
3 4
All four 1x1 submatrices have element sum at most x = 5. The 2x1 submatrix containing 1 and 3 and the 1x2 submatrix containing 1 and 2 also have element sums 1+3 = 4 and 1+2 = 3, which are at most x, so they satisfy the condition. Every other submatrix has element sum greater than 5, so the answer is 6.
As another example, let N = 2, M = 3, x = 0, and let A be as follows.
0 -1 -2
-3 -4 -5
Every submatrix of A has element sum at most 0, so the answer is 18.
Write a program that takes N, M, x, and A as input and counts the submatrices whose element sum is at most x.
Input
The first line contains the number of test cases T.
The first line of each test case contains N, M, and x separated by spaces.
The next N lines each contain M integers separated by spaces.
Output
Print the number of submatrices of A whose element sum is at most x.
Constraints
- 1 ≤ T ≤ 10
- -1,000,000,000 ≤ x ≤ 1,000,000,000
- -100,000 ≤ each element of A ≤ 100,000