結果

問題 No.866 レベルKの正方形
ユーザー lam6er
提出日時 2025-04-16 01:08:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,804 bytes
コンパイル時間 400 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 104,232 KB
最終ジャッジ日時 2025-04-16 01:10:13
合計ジャッジ時間 8,733 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 8 TLE * 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)]
    res = 0

    for s in range(1, min(H, W) + 1):
        # Precompute mask for each column j, for each possible i (bottom row)
        # mask[j] will be a list where mask[j][i] is the bitmask for column j up to row i
        # But this is memory-intensive. Instead, compute mask for each i incrementally.
        for i in range(s - 1, H):
            # Compute the current mask for each column j
            mask = []
            for j in range(W):
                unique = set()
                for row in range(i - s + 1, i + 1):
                    unique.add(grid[row][j])
                m = 0
                for c in unique:
                    m |= 1 << (ord(c) - ord('a'))
                mask.append(m)
            # Now compute the number of horizontal windows of size s with OR having K bits set
            # We can precompute the prefix ORs for efficiency
            current_or = 0
            count = 0
            # Initialize the first window
            for jj in range(s):
                current_or |= mask[jj]
            if bin(current_or).count('1') == K:
                count += 1
            # Slide the window
            for j in range(1, W - s + 1):
                # Remove the leftmost element (can't do it, so recompute OR)
                # This is O(s) time, which is too slow for large s
                # Instead, recompute the OR for the new window
                current_or = 0
                for jj in range(j, j + s):
                    current_or |= mask[jj]
                if bin(current_or).count('1') == K:
                    count += 1
            res += count
    print(res)

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