Problem Description

Given an $N \times M$ matrix $A$, please count how many submatrices (minimum $1 \times 1$, maximum $N \times M$) satisfy that the sum of all numbers in the submatrix does not exceed the given integer $K$.

Input Format

The first line contains three integers $N$, $M$, and $K$.

Then there are $N$ lines, each containing $M$ integers, representing the matrix $A$.

Output Format

Output one integer representing the answer.

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

19

Hint

[Sample Explanation]

There are $19$ submatrices that satisfy the condition, including:

There are $10$ of size $1 \times 1$.

There are $3$ of size $1 \times 2$.

There are $2$ of size $1 \times 3$.

There is $1$ of size $1 \times 4$.

There are $3$ of size $2 \times 1$.

[Test Case Scale and Constraints]

For $30\%$ of the testdata, $N, M \leq 20$.

For $70\%$ of the testdata, $N, M \leq 100$.

For $100\%$ of the testdata, $1 \leq N, M \leq 500$, $0 \leq A_{i j} \leq 1000$, $1 \leq K \leq 2.5\times10^8$.

Lanqiao Cup 2022 Provincial Contest B Group, Problem F.

Translated by ChatGPT 5