2659 问题 S: 蓝桥杯2022年第十三届省赛真题-统计子矩阵

时间限制: 1s 内存限制: 256MB 提交: 8642 解决: 1751
题目描述
给定一个 N × M 的矩阵 A,请你统计有多少个子矩阵 (最小 1 × 1,最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K? 
输入

第一行包含三个整数 N, M 和 K. 

之后 N 行每行包含 M 个整数,代表矩阵 A.

输出
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
19
提示

满足条件的子矩阵一共有 19,包含:

大小为 1 × 1 的有 10 个。

大小为 1 × 2 的有 3 个。

大小为 1 × 3 的有 2 个。

大小为 1 × 4 的有 1 个。

大小为 2 × 1 的有 3 个。

对于 30% 的数据,N, M ≤ 20. 对于 70% 的数据,N, M ≤ 100. 

对于 100% 的数据,1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

比赛公告

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊