Save the nature
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian
The new king of Byteland, John-2318, has just ascended the throne. As every new king, he wants to build a spectacular palace to showcase his wealth and power.
We can consider Byteland as an N x M rectangular matrix A. If A[i][j] is positive, then it means that A[i][j] litres of oxygen are produced by trees in the cell with coordinates (i, j) every day. On the other hand, a negative value of A[i][j] indicates that a Byteland resident lives in this cell, who consumes A[i][j] litres of oxygen every day.
The palace will occupy some rectangle submatrix of A. All the cells within the palace premises will not produce nor consume any oxygen.
Byteland scientists discovered the new important fact: if Byteland will be producing S less litres of oxygen every day than it produces now, it will lead to a natural disaster. So now everyone is interested in the following question: how many ways exist for choosing a rectangular region for the planned palace?
The first line contains one integer T denoting the number of testcases.
Each testcase starts with a line containing three space-separated integers N, M, and S. The following N lines contain M integers each and describe the cells of the matrix A.
For each testcase, output a single line containing one integer - the number of rectangles where the palace can be built without causing a disaster.
- 1 ≤ T ≤ 10
- 1 ≤ N, M ≤ 150
- -109 ≤ A[i][j] ≤ 109
- 1 ≤ S ≤ 109
- Subtask 1 (27 points) 1 ≤ N, M ≤ 20, time limit = 1 sec
- Subtask 2 (30 points) 1 ≤ N, M ≤ 50, time limit = 1 sec
- Subtask 3 (43 points) 1 ≤ N, M ≤ 150, time limit = 3 sec
Input: 2 2 3 7 1 2 3 4 5 6 3 3 12 3 3 3 4 4 4 3 3 3 Output: 11 27
Test case 1: we have the following matrix A:
1 2 3
4 5 6
There are 11 rectangular submatrices with sum ≤ S = 7: all the 6 cells themselves, 2 columns (the left and the middle), 1 row (the first), and 2 segments in the first row of length 2 each.
|Tags||fenwick, ltime29, medium, mergesort, pavel1996|
|Time Limit:||1 - 3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.