/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 550 点
問題文
N \times M のグリッドが与えられます。各マスには . または # が書かれています。
マスに書かれている記号の情報は N 個の文字列 S_1,S_2,\dots,S_N として与えられ、上から i 行目の左から j マス目には S_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
- 全ての l_x \le i \le r_x 、 l_y \le j \le r_y を満たす整数組 (i,j) について、上から 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) で表現される長方領域
- 縦 1 マス、横 2 マスの
.のみからなる長方領域 4 個 - 縦 2 マス、横 1 マスの
.のみからなる長方領域 4 個 - 縦 1 マス、横 1 マスの
.のみからなる長方領域 7 個
入力例 2
7 5 35 ..... ..... ..... ..... ..... ..... .....
出力例 2
420
入力例 3
10 9 25 #.....#.. ....#.... .......#. ......... .......#. .#....... ......... #........ ........# .#.....#.
出力例 3
984
Score : 550 points
Problem Statement
You are given an N \times M grid. Each cell contains either . or #.
The information about the symbols written in the cells is given as N strings S_1,S_2,\dots,S_N, where the same symbol as the j-th character of S_i is written in the cell at the i-th row from the top and j-th column from the left.
How many rectangular regions consisting of at most K cells have all cells containing .?
Formally, count the number of integer tuples (l_x,r_x,l_y,r_y) that satisfy the following conditions:
- 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
- For all integer pairs (i,j) satisfying l_x \le i \le r_x and l_y \le j \le r_y, the cell at the i-th row from the top and j-th column from the left contains
..
Constraints
- N, M, and K are integers.
- 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 is a string of length M consisting of
.and#.
Input
The input is given from Standard Input in the following format:
N M K S_1 S_2 \vdots S_N
Output
Output the answer.
Sample Input 1
3 3 4 #.. ... ..#
Sample Output 1
19
The rectangular regions to count are the following 19:
- A rectangular region represented by (l_x,r_x,l_y,r_y) = (1,2,2,3)
- A rectangular region represented by (l_x,r_x,l_y,r_y) = (2,3,1,2)
- A rectangular region represented by (l_x,r_x,l_y,r_y) = (2,2,1,3)
- A rectangular region represented by (l_x,r_x,l_y,r_y) = (1,3,2,2)
- 4 rectangular regions of 1 row and 2 columns consisting only of
. - 4 rectangular regions of 2 rows and 1 column consisting only of
. - 7 rectangular regions of 1 row and 1 column consisting only of
.
Sample Input 2
7 5 35 ..... ..... ..... ..... ..... ..... .....
Sample Output 2
420
Sample Input 3
10 9 25 #.....#.. ....#.... .......#. ......... .......#. .#....... ......... #........ ........# .#.....#.
Sample Output 3
984