結果

問題 No.866 レベルKの正方形
ユーザー gew1fw
提出日時 2025-06-12 21:09:57
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,156 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,708 KB
実行使用メモリ 849,076 KB
最終ジャッジ日時 2025-06-12 21:10:53
合計ジャッジ時間 5,081 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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):
            row = [0]*(W+1)
            for j in range(1, W+1):
                row[j] = row[j-1] + (1 if grid[i-1][j-1] == c else 0)
                pre[i][j] = pre[i-1][j] + row[j]
        prefix[c] = pre
    
    result = 0
    max_s = min(H, W)
    for s in range(1, max_s+1):
        for a in range(1, H - s + 2):
            for b in range(1, W - s + 2):
                x1, y1 = a, b
                x2, y2 = a + s - 1, b + s - 1
                distinct = 0
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    sum_c = prefix[c][x2][y2] - prefix[c][x1-1][y2] - prefix[c][x2][y1-1] + prefix[c][x1-1][y1-1]
                    if sum_c > 0:
                        distinct += 1
                if distinct == K:
                    result += 1
    print(result)

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