No.866 レベルKの正方形
レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 57
作問者 :
e869120
/ テスター :
tatyam
タグ : / 解いたユーザー数 57
作問者 :
e869120
/ テスター :
tatyam
問題文最終更新日: 2019-08-16 21:17:54
問題文
注意：この問題は高速な言語でなければ実行時間制限に間に合わない可能性があります。
$H$ * $W$ のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。左上のマスは $(1, 1)$、右下のマスは $(H, W)$ となります。
さて、マス $(i, j)$ には英小文字 $c_{i, j}$ が書かれています。
左上のマスが $(a, b)$, 右下のマスが $(c, d)$ $(1 \leq a \leq c \leq H, 1 \leq b \leq d \leq W, c-a=d-b)$ である正方形領域について、この正方形領域の中に含まれる文字の種類数がちょうど $P$ 種類の時、この正方形を「レベル $P$ の正方形」とします。
レベル $K$ の正方形がいくつ存在するか求めて下さい。
制約
全ての入力データは以下の制約を満たします。
- $H, W$ は $1$ 以上 $2 \ 000$ 以下の整数
- $K$ は $1$ 以上 $26$ 以下の整数
- $c_{i, j}$ は
aからzまでの英小文字のうちいずれかである
入力
$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}$
出力
最後に改行してください。
サンプル
サンプル1
入力
4 4 6 abcd bcde cdef defg
出力
0
条件を満たす正方形領域はありません。
サンプル2
入力
4 4 3 abcd bcde cdef defg
出力
9
以下の $9$ 個の正方形領域が条件を満たします。
- 左上 $(1, 1)$, 右下 $(2, 2)$ の正方形領域
- 左上 $(1, 2)$, 右下 $(2, 3)$ の正方形領域
- 左上 $(1, 3)$, 右下 $(2, 4)$ の正方形領域
- 左上 $(2, 1)$, 右下 $(3, 2)$ の正方形領域
- 左上 $(2, 2)$, 右下 $(3, 3)$ の正方形領域
- 左上 $(2, 3)$, 右下 $(3, 4)$ の正方形領域
- 左上 $(3, 1)$, 右下 $(4, 2)$ の正方形領域
- 左上 $(3, 2)$, 右下 $(4, 3)$ の正方形領域
- 左上 $(3, 3)$, 右下 $(4, 4)$ の正方形領域
サンプル3
入力
20 20 13 ncununuineuinouicnur nhuimjiehuiomiojioje jimiomuimmdrwumuioer mimiajifhpmiowjiojor kiojioansngimumapois jimuipammhupheohmudp hunpumimhuewijfuhrur jipamuyfiuhrmpvyxphu jiamsmxoyuuwhdehuutr ioamuusuieumhufupyrr mopmuaiomdumruuruype popuauximueimurmfumr ouiweuyoduwiumfryisj koklnxuamurhphuremeu immuwmupmpunyaygyweh mumhxeyomxbwuhamhisd moumzuihmyoetyrouish zamuepiioouuomeymgoa mamouzhoiedieoygmoer upahumgeyurogebyjajd
出力
119
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。