結果

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

ソースコード

diff # 

import sys

def main():
    H, W, K = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append([c for c in line])
    
    # 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] + (1 if grid[i-1][j-1] == c else 0)
        prefix[c] = pre
    
    result = 0
    max_s = min(H, W)
    for s in range(1, max_s + 1):
        for i in range(1, H - s + 2):
            for j in range(1, W - s + 2):
                count = 0
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    x1, y1 = i, j
                    x2, y2 = i + s - 1, j + s - 1
                    total = prefix[c][x2][y2] - prefix[c][x1-1][y2] - prefix[c][x2][y1-1] + prefix[c][x1-1][y1-1]
                    if total > 0:
                        count += 1
                if count == K:
                    result += 1
    print(result)

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