241970 - 元素和小于等于 K 的子矩阵的数目

题目描述

给定一个 m 行 n 列的非负整数矩阵 a,以及一个整数 K。 请统计满足以下条件的子矩阵数量:

  1. 子矩阵必须包含原矩阵左上角的元素 a_{1,1}。
  2. 子矩阵中所有元素的和小于等于 K。 一个子矩阵由原矩阵中连续的若干行和连续的若干列组成。由于它必须包含 a_{1,1},因此必然由第 1 行至第 i 行、第 1 列至第 j 列构成,其中 1 \le i \le m,1 \le j \le n。
输入

第一行输入三个整数 m、n 和 K,分别表示矩阵的行数、列数和元素和的上限。 接下来 m 行,每行包含 n 个整数,第 i 行的第 j 个整数表示 a_{i,j}。

输出

输出一个整数,表示满足条件的子矩阵数量。

样例

输入

2 3 18
7 6 3
6 6 1

输出

4

输入

3 3 20
7 2 9
1 5 0
2 6 6

输出

6
说明

数据范围:

  • 1 \le m,n \le 1000;
  • 0 \le a_{i,j} \le 1000;
  • 1 \le K \le 10^9

样例解释 1 满足条件的 4 个子矩阵,其右下角坐标分别为 (1,1)、(1,2)、(1,3) 和 (2,1),对应的元素和分别为 7、13、16 和 13,均小于等于 18。

样例解释 2 满足条件的 6 个子矩阵,其右下角坐标分别为 (1,1)、(1,2)、(1,3)、(2,1)、(2,2) 和 (3,1),对应的元素和分别为 7、9、18、8、15 和 10,均小于等于 20。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 20
通过人数 14
金币数量 3 枚
难度 入门


上一题 下一题