結果

問題 No.866 レベルKの正方形
ユーザー gew1fw
提出日時 2025-06-12 16:19:04
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,237 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,356 KB
実行使用メモリ 849,012 KB
最終ジャッジ日時 2025-06-12 16:19:41
合計ジャッジ時間 4,781 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 MLE * 1 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(H)]
    
    # Precompute prefix sums for each character
    prefix = {}
    for c in 'abcdefghijklmnopqrstuvwxyz':
        pre = [[0]*(W+1) for _ in range(H+1)]
        for i in range(1, H+1):
            for j in range(1, W+1):
                pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1]
                if grid[i-1][j-1] == c:
                    pre[i][j] += 1
        prefix[c] = pre
    
    max_s = min(H, W)
    ans = 0
    
    for s in range(1, max_s + 1):
        if s > H or s > W:
            continue
        for i in range(H - s + 1):
            for j in range(W - s + 1):
                a = i + 1
                b = j + 1
                c_ = a + s - 1
                d_ = b + s - 1
                count = 0
                for char in 'abcdefghijklmnopqrstuvwxyz':
                    pre = prefix[char]
                    total = pre[c_][d_] - pre[a-1][d_] - pre[c_][b-1] + pre[a-1][b-1]
                    if total > 0:
                        count += 1
                if count == K:
                    ans += 1
    print(ans)

if __name__ == "__main__":
    main()
0