結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー mkawa2
提出日時 2021-05-24 23:51:38
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,236 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 577,068 KB
最終ジャッジ日時 2024-10-13 08:09:36
合計ジャッジ時間 9,969 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 7 TLE * 1 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def II(): return int(sys.stdin.buffer.readline())
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def BI(): return sys.stdin.buffer.readline().rstrip()
inf = 10**16

h, w, k = LI()
max_e = min(h, w).bit_length()-1
tt = [[0]*h*w for _ in range(max_e+1)]
tt[0] = [1 << c-97 for _ in range(h) for c in BI()]

for e in range(max_e):
    d = 1 << e
    for i in range(h):
        if i+d*2 > h: break
        for j in range(w):
            if j+d*2 > w: break
            ij = i*w+j
            tt[e+1][ij] = tt[e][ij] | tt[e][ij+d] | tt[e][ij+d*w] | tt[e][ij+d*w+d]

# i行目[l,r]を1辺とする正方形内の文字種類数
def cnt_in_square(i, l, r):
    d = r-l+1
    if i+d > h: return inf
    if l == r: return 1
    e = (d-1).bit_length()-1
    m = d-(1 << e)
    ij = i*w+l
    s = tt[e][ij] | tt[e][ij+m] | tt[e][ij+m*w] | tt[e][ij+m*w+m]
    return bin(s).count("1")

ans = 0
for i in range(h):
    r0 = r1 = 0
    for l in range(w):
        if r0 < l: r0 = l
        while r0 < w and cnt_in_square(i, l, r0) < k:
            r0 += 1
        if r0 == w: break
        if r1 < r0: r1 = r0
        while r1 < w and cnt_in_square(i, l, r1) <= k:
            r1 += 1
        ans += r1-r0

print(ans)
0