結果

問題 No.866 レベルKの正方形
ユーザー gew1fw
提出日時 2025-06-12 16:16:35
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,599 bytes
コンパイル時間 270 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 852,352 KB
最終ジャッジ日時 2025-06-12 16:17:52
合計ジャッジ時間 4,859 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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
    
    count = 0
    
    # Iterate over all possible square sizes
    max_s = min(H, W)
    for s in range(1, max_s + 1):
        # Iterate over all possible top-left corners
        for i in range(1, H - s + 2):
            for j in range(1, W - s + 2):
                # Check each character
                distinct = 0
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    # Compute the sum in the square
                    top_row = i
                    bottom_row = i + s - 1
                    left_col = j
                    right_col = j + s - 1
                    # Get the prefix sum for character c
                    pre = prefix[c]
                    # Calculate sum in the square
                    total = pre[bottom_row][right_col] - pre[top_row-1][right_col] - pre[bottom_row][left_col-1] + pre[top_row-1][left_col-1]
                    if total > 0:
                        distinct += 1
                if distinct == K:
                    count += 1
    
    print(count)

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