[蓝桥杯 2022 省 B] 统计子矩阵
题目描述
给定一个 $N \times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \times 1$, 最大 $N \times M)$ 满足子矩阵中所有数的和不超过给定的整数 $K$。
输入输出格式
输入格式
第一行包含三个整数 $N, M$ 和 $K$。
之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$。
输出格式
一个整数代表答案。
输入输出样例
输入样例 #1
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12输出样例 #1
19说明
**【样例说明】**
满足条件的子矩阵一共有 $19$，包含:
大小为 $1 \times 1$ 的有 $10$ 个。
大小为 $1 \times 2$ 的有 $3$ 个。 大小为 $1 \times 3$ 的有 $2$ 个。
大小为 $1 \times 4$ 的有 $1$ 个。
大小为 $2 \times 1$ 的有 $3$ 个。
**【评测用例规模与约定】**
对于 $30 \%$ 的数据, $N, M \leq 20$.
对于 $70 \%$ 的数据, $N, M \leq 100$.
对于 $100 \%$ 的数据, $1 \leq N, M \leq 500,0 \leq A_{i j} \leq 1000,1 \leq K \leq 2.5\times10^8$.
蓝桥杯 2022 省赛 B 组 F 题。