← 返回题目列表

AtCoder · abc420_f

I. 切努奇

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

分数: 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