P13647 [NOISG 2016] Fabric

Kraw the Krow 有一块漂亮的布料。布料上的花纹非常精致，以至于每一部分都不相同。然而，在 2017 年的大火之后，这块布料上出现了许多难看的洞。（当然，这场大火是由 Squeaky the Rat 引发的。） Kraw 想要忘记那场大火，因为他并不喜欢高温。他希望能从布料上裁剪出一个矩形，把剩下的部分都扔掉。新的布料必须满足面积至少为 $K$，并且不能包含任何洞。 由于 Kraw 的布料具有“规-反对称”特性（或者别的什么——Kraw 已经不记得推销员说了什么），Kraw 只能沿着规则的网格线裁剪布料。Kraw 想知道，有多少种方法可以裁剪出一个面积至少为 $K$、且不包含任何洞的矩形。

你的程序应从标准输入读取数据。输入包括： - 一行，包含三个整数 $N$ 和 $M$（$1 \leq N, M \leq 2000$），分别表示布料的高度和宽度，以及 $K$（$1 \leq K \leq MN$），即矩形的最小面积（以网格单元数计）； - 接下来 $N$ 行，每行包含 $M$ 个整数 $s_{0y}, s_{1y}, \ldots, s_{(M-1)y}$。若坐标为 $(x, y)$ 的网格单元有洞，则 $s_{xy} = 1$，否则 $s_{xy} = 0$。

输出一行，包含一个整数：表示可以裁剪出多少种面积至少为 $K$、且不包含任何洞的矩形。

### 样例解释 可以从布料上裁剪出 3 个面积至少为 3 的矩形。以左上角为 $(0, 0)$，它们分别是： - 2 个面积为 3 的矩形——$\{(1, 0), (2, 0), (3, 0)\}$，$\{(0, 1), (1, 1), (2, 1)\}$ - 1 个面积为 4 的矩形——$\{(1, 0), (2, 0), (1, 1), (2, 1)\}$ ### 子任务 每组数据的最大运行时间为 1.0 秒。你的程序将在以下输入范围内进行测试： | 子任务 | 分值 | 限制条件 | | :-: | :-: | :-: | | 1 | 7 | 满足 $0 < N, M \leq 2000$，$K = 1$ 且所有 $(x, y)$ 都有 $s_{xy} = 0$； | | 2 | 9 | 满足 $0 < N, M \leq 2000$，$K = 1$ 且仅有一个 $(x, y)$ 满足 $s_{xy} = 1$； | | 3 | 12 | 满足 $0 < N, M \leq 50$； | | 4 | 14 | 满足 $0 < N, M \leq 500$； | | 5 | 23 | 满足 $0 < N, M \leq 2000$ 且 $K = 1$； | | 6 | 35 | 满足 $0 < N, M \leq 2000$。 | 由 ChatGPT 4.1 翻译