← 返回题目列表

AtCoder · abc461_d

D. 计数子网格总和 = K

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

分数: 425 点

问题陈述

有一个 H \times W 网格,每个单元格包含一个整数 0 or 1.
每个单元格中写入的整数信息如下 H 字符串 S_1, S_2, \dots, S_H 长度 W。 如果 j- 第一个字符 S_i is 0,那么 0 写入位于 i从顶部开始的第行和 j- 网格左侧的第列;如果 j- 第一个字符 S_i is 1,那么 1 写入该单元格中。

找出写入的整数之和等于的矩形区域的数量 K.
更正式地说,求整数四元组的个数 (r_1, c_1, r_2, c_2) 满足以下所有条件:

  • 1 \le r_1 \le r_2 \le H
  • 1 \le c_1 \le c_2 \le W
  • 写入单元格中的整数之和 i从顶部开始的第行和 j- 从左侧算起的所有整数对上的第列 (i, j) 满意 r_1 \le i \le r_2, c_1 \le j \le c_2,等于 K.

约束

  • H 和 W 是介于 1 和 500,包括在内。
  • K 是介于 0 和 HW,包括在内。
  • S_i 是一个长度为的字符串 W 组成 0 和 1.

输入

输入由标准输入按以下格式给出:

H W K
S_1
S_2
\vdots
S_H

输出

输出答案。


示例输入 1

3 4 3
1001
1101
0110

示例输出 1

8

有八个矩形区域,其中写入的整数之和等于 K:

  • 从行中提取的矩形区域 1 到行 2 从顶部和列 1 转至专栏 2 从左起
  • 从行中提取的矩形区域 1 到行 2 从顶部和列 1 转至专栏 3 从左起
  • 从行中提取的矩形区域 1 到行 2 从顶部和列 2 转至专栏 4 从左起
  • 从行中提取的矩形区域 1 到行 3 从顶部和列 2 转至专栏 3 从左起
  • 从行中提取的矩形区域 1 到行 3 从顶部和列 3 转至专栏 4 从左起
  • 从行中提取的矩形区域 2 到行 2 从顶部和列 1 转至专栏 4 从左起
  • 从行中提取的矩形区域 2 到行 3 从顶部和列 1 转至专栏 2 从左起
  • 从行中提取的矩形区域 2 到行 3 从顶部和列 2 转至专栏 3 从左起

示例输入 2

5 4 20
0101
1010
0101
1010
0101

示例输出 2

0

示例输入 3

15 20 17
10111101101100000100
01100000000010000011
01110010111000111000
11001100000111011000
10100001100011100010
01101000101010000101
10110001111110000100
10110011101100101101
01010001110011001001
01010110010001100110
01110100011110011110
01100000100111010010
11001101100111101100
10111100010101111011
00101101011100010000

示例输出 3

448