← 返回题目列表

Codeforces · 364/E

E. 空矩形

中文机器翻译题面 查看原题

你有一个 n × m 的表格(n 行和 m 列),表格的每个单元格包含一个“0”或一个“1”。

您的任务是计算边与表格边平行并沿着单元格边框的矩形的数量,使得数字 1 在矩形中恰好出现 k 次。

输入

第一行包含三个空格分隔的整数 n、m 和 k (1 ≤ n, m ≤ 2500, 0 ≤ k ≤ 6) — 表格的大小和所需的数字个数。

接下来的 n 行每行包含 m 个字符“0”或“1”。第 j 行的第 i 个字符对应于表的第 j 行第 i 列中的字符。

输出

打印单个数字 — 恰好包含 k 个数字 1 的矩形的数量。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3 3 2
101
000
101

输出 #1

8

输入 #2

5 5 1
00000
00000
00100
00000
00000

输出 #2

81

输入 #3

5 5 6
01010
10101
01010
10101
01010

输出 #3

12

输入#4

3 3 0
001
010
000

输出#4

15

输入 #5

4 4 0
0000
0101
0000
0000

输出 #5

52