結果

問題 No.2456 Stamp Art
ユーザー gew1fw
提出日時 2025-06-12 12:52:48
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,436 bytes
コンパイル時間 275 ms
コンパイル使用メモリ 82,300 KB
実行使用メモリ 513,852 KB
最終ジャッジ日時 2025-06-12 12:54:05
合計ジャッジ時間 29,755 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    H, W = map(int, sys.stdin.readline().split())
    grid = []
    for _ in range(H):
        line = sys.stdin.readline().strip()
        grid.append(line)
    
    # Convert grid to binary matrix (1 for black, 0 for white)
    bin_grid = [[0]*(W+1) for _ in range(H+1)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                bin_grid[i+1][j+1] = 1
    
    # Compute prefix sums
    prefix = [[0]*(W+2) for _ in range(H+2)]
    for i in range(1, H+1):
        row_sum = 0
        for j in range(1, W+1):
            row_sum += bin_grid[i][j]
            prefix[i][j] = prefix[i-1][j] + row_sum
    
    low = 1
    high = min(H, W)
    answer = 0
    
    while low <= high:
        mid = (low + high) // 2
        valid = False
        
        # Initialize difference array
        diff = [[0]*(W+2) for _ in range(H+2)]
        found = False
        
        for i in range(1, H - mid + 2):
            for j in range(1, W - mid + 2):
                a = i
                b = j
                c = a + mid - 1
                d = b + mid - 1
                if c > H or d > W:
                    continue
                # Calculate sum using prefix sums
                total = prefix[c][d] - prefix[a-1][d] - prefix[c][b-1] + prefix[a-1][b-1]
                if total == mid * mid:
                    # Mark the square in the difference array
                    diff[a][b] += 1
                    diff[a][d+1] -= 1
                    diff[c+1][b] -= 1
                    diff[c+1][d+1] += 1
                    found = True
        
        # Compute coverage using the difference array
        coverage = [[0]*(W+2) for _ in range(H+2)]
        all_covered = True
        
        for i in range(1, H+1):
            row_sum = 0
            for j in range(1, W+1):
                row_sum += diff[i][j]
                coverage[i][j] = coverage[i-1][j] + row_sum
        
        # Check all black cells
        for i in range(1, H+1):
            for j in range(1, W+1):
                if bin_grid[i][j] == 1 and coverage[i][j] <= 0:
                    all_covered = False
                    break
            if not all_covered:
                break
        
        if all_covered and found:
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    
    print(answer)

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