分数: 550 点
问题陈述
您将获得 N \times M 网格。每个单元格包含 . or #.
有关单元格中写入的符号的信息给出为 N 字符串 S_1,S_2,\dots,S_N,其中符号与 j- 第一个字符 S_i 写入位于 i从顶部算起的第行和 j左起第 列。
最多由多少个矩形区域组成 K 单元格具有包含以下内容的所有单元格 .?
正式地,计算整数元组的数量 (l_x,r_x,l_y,r_y) 满足以下条件:
- 1 \le l_x \le r_x \le N
- 1 \le l_y \le r_y \le M
- (r_x-l_x+1) \times (r_y-l_y+1) \le K
- 对于所有整数对 (i,j) 满意 l_x \le i \le r_x 和 l_y \le j \le r_y,位于 i从顶部算起的第行和 j左起第 列包含
..
约束
- N, M,和 K 是整数。
- 1 \le N,M \le 5 \times 10^5
- 1 \le N \times M \le 5 \times 10^6
- 1 \le K \le N \times M
- S_i 是一个长度为的字符串 M 组成
.和#.
输入
输入由标准输入按以下格式给出:
N M K S_1 S_2 \vdots S_N
输出
输出答案。
示例输入 1
3 3 4 #.. ... ..#
示例输出 1
19
要计数的矩形区域如下 19:
- 表示的矩形区域 (l_x,r_x,l_y,r_y) = (1,2,2,3)
- 表示的矩形区域 (l_x,r_x,l_y,r_y) = (2,3,1,2)
- 表示的矩形区域 (l_x,r_x,l_y,r_y) = (2,2,1,3)
- 表示的矩形区域 (l_x,r_x,l_y,r_y) = (1,3,2,2)
- 4 的矩形区域 1 行和 2 列仅包含
. - 4 的矩形区域 2 行和 1 列仅包含
. - 7 的矩形区域 1 行和 1 列仅包含
.
示例输入 2
7 5 35 ..... ..... ..... ..... ..... ..... .....
示例输出 2
420
示例输入 3
10 9 25 #.....#.. ....#.... .......#. ......... .......#. .#....... ......... #........ ........# .#.....#.
示例输出 3
984