Responsive image

问题 F: 第十三届蓝桥杯大赛-试题 F: 统计子矩阵

问题 F: 第十三届蓝桥杯大赛-试题 F: 统计子矩阵

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 21
[提交][状态][讨论版][命题人:]

题目描述

给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

输入描述

第一行包含三个整数 N, M 和 K. 之后 N 行每行包含 M 个整数，代表矩阵 A. 
对于 30% 的数据，N, M ≤ 20. 
对于 70% 的数据，N, M ≤ 100. 
对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

输出描述

一个整数代表答案。

样例输入

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 个。

[提交][状态]
ACM算法攻关部