← 返回题目
题库练习 Empty Rectangles
← 上一题 下一题 →

A9197 | Empty Rectangles

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

You've got an $n×m$ table ( $n$ rows and $m$ columns), each cell of the table contains a "0" or a "1".

Your task is to calculate the number of rectangles with the sides that are parallel to the sides of the table and go along the cell borders, such that the number one occurs exactly $k$ times in the rectangle.

输入格式

The first line contains three space-separated integers $n$ , $m$ and $k$ ( $1<=n,m<=2500$ , $0<=k<=6$ ) — the sizes of the table and the required number of numbers one.

Next $n$ lines each contains $m$ characters "0" or "1". The $i$ -th character of the $j$ -th line corresponds to the character that is in the $j$ -th row and the $i$ -th column of the table.

输出格式

Print a single number — the number of rectangles that contain exactly $k$ numbers one.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入 #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
C++ 编辑器
输入
输出