No.866 Level K Squares
e869120
tatyamProblem Statement
Note: this problem may not finish within the time limit unless you use a fast language.
There is a grid of $H$ * $W$ cells. The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by $(i, j)$. The top-left cell is $(1, 1)$ and the bottom-right cell is $(H, W)$.
The cell $(i, j)$ contains a lowercase English letter $c_{i, j}$.
For a square region whose top-left cell is $(a, b)$ and whose bottom-right cell is $(c, d)$ $(1 \leq a \leq c \leq H, 1 \leq b \leq d \leq W, c-a=d-b)$, if the number of distinct letters contained in the square region is exactly $P$, the square is called a "level $P$ square".
Find how many level $K$ squares exist.
Constraints
All input data satisfy the following constraints.
- $H, W$ are integers between $1$ and $2 \ 000$, inclusive
- $K$ is an integer between $1$ and $26$, inclusive
- $c_{i, j}$ is one of the lowercase English letters from
atoz
Input
$H$ $W$ $K$
$c_{1, 1}c_{1, 2}c_{1, 3}$...$c_{1, W}$
$c_{2, 1}c_{2, 2}c_{2, 3}$...$c_{2, W}$
$c_{3, 1}c_{3, 2}c_{3, 3}$...$c_{3, W}$
...
$c_{H, 1}c_{H, 2}c_{H, 3}$...$c_{H, W}$
Output
Print a newline at the end.
Sample
Sample 1
Input
4 4 6 abcd bcde cdef defg
Output
0
No square region satisfies the condition.
Sample 2
Input
4 4 3 abcd bcde cdef defg
Output
9
The following $9$ square regions satisfy the condition.
- The square region with top-left $(1, 1)$ and bottom-right $(2, 2)$
- The square region with top-left $(1, 2)$ and bottom-right $(2, 3)$
- The square region with top-left $(1, 3)$ and bottom-right $(2, 4)$
- The square region with top-left $(2, 1)$ and bottom-right $(3, 2)$
- The square region with top-left $(2, 2)$ and bottom-right $(3, 3)$
- The square region with top-left $(2, 3)$ and bottom-right $(3, 4)$
- The square region with top-left $(3, 1)$ and bottom-right $(4, 2)$
- The square region with top-left $(3, 2)$ and bottom-right $(4, 3)$
- The square region with top-left $(3, 3)$ and bottom-right $(4, 4)$
Sample 3
Input
20 20 13 ncununuineuinouicnur nhuimjiehuiomiojioje jimiomuimmdrwumuioer mimiajifhpmiowjiojor kiojioansngimumapois jimuipammhupheohmudp hunpumimhuewijfuhrur jipamuyfiuhrmpvyxphu jiamsmxoyuuwhdehuutr ioamuusuieumhufupyrr mopmuaiomdumruuruype popuauximueimurmfumr ouiweuyoduwiumfryisj koklnxuamurhphuremeu immuwmupmpunyaygyweh mumhxeyomxbwuhamhisd moumzuihmyoetyrouish zamuepiioouuomeymgoa mamouzhoiedieoygmoer upahumgeyurogebyjajd
Output
119
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。