luogu#P8783. [蓝桥杯 2022 省 B] 统计子矩阵

    ID: 12768 远端评测题 1000ms 128MiB 尝试: 1 已通过: 1 难度: 3 上传者: 标签>2022枚举双指针,two-pointer蓝桥杯省赛

[蓝桥杯 2022 省 B] 统计子矩阵

题目描述

给定一个 N×MN \times M 的矩阵 AA,请你统计有多少个子矩阵 (最小 1×11 \times 1, 最大 N×M)N \times M) 满足子矩阵中所有数的和不超过给定的整数 KK

输入格式

第一行包含三个整数 N,MN, MKK

之后 NN 行每行包含 MM 个整数, 代表矩阵 AA

输出格式

一个整数代表答案。

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

提示

【样例说明】

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

大小为 1×11 \times 1 的有 1010 个。

大小为 1×21 \times 2 的有 33 个。 大小为 1×31 \times 3 的有 22 个。

大小为 1×41 \times 4 的有 11 个。

大小为 2×12 \times 1 的有 33 个。

【评测用例规模与约定】

对于 30%30 \% 的数据, N,M20N, M \leq 20.

对于 70%70 \% 的数据, N,M100N, M \leq 100.

对于 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 题。