結果

問題 No.2456 Stamp Art
ユーザー lam6er
提出日時 2025-04-15 22:07:23
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 2,615 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 81,912 KB
実行使用メモリ 849,408 KB
最終ジャッジ日時 2025-04-15 22:08:55
合計ジャッジ時間 5,653 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

H, W = map(int, input().split())
grid = [input().strip() for _ in range(H)]

# Compute prefix sum for 2D range sum queries
prefix = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    row = grid[i-1]
    for j in range(1, W + 1):
        prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + (1 if row[j-1] == '#' else 0)

# Precompute black cells for each row
black_rows = [[] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            black_rows[i].append(j)

low = 1
high = min(H, W)
ans = 0

while low <= high:
    mid = (low + high) // 2
    valid_squares = []
    max_a = H - mid + 1
    max_b = W - mid + 1

    if max_a < 1 or max_b < 1:
        high = mid - 1
        continue

    for a in range(1, max_a + 1):
        a_end = a + mid - 1
        for b in range(1, max_b + 1):
            b_end = b + mid - 1
            total = prefix[a_end][b_end] - prefix[a-1][b_end] - prefix[a_end][b-1] + prefix[a-1][b-1]
            if total == mid * mid:
                valid_squares.append((a, b))

    # Track intervals for each row
    from collections import defaultdict
    intervals = defaultdict(list)
    for a, b in valid_squares:
        start_row = a - 1  # Convert to 0-based
        end_row = (a + mid - 1) - 1
        start_col = b - 1
        end_col = (b + mid - 1) - 1
        for row in range(start_row, end_row + 1):
            intervals[row].append((start_col, end_col))

    # Check each row's coverage
    ok = True
    for i in range(H):
        if not black_rows[i]:
            continue
        if i not in intervals:
            ok = False
            break
        current_intervals = intervals[i]
        current_intervals.sort()
        merged = []
        for interval in current_intervals:
            if not merged:
                merged.append(interval)
            else:
                last = merged[-1]
                if interval[0] <= last[1] + 1:
                    new_start = last[0]
                    new_end = max(last[1], interval[1])
                    merged[-1] = (new_start, new_end)
                else:
                    merged.append(interval)
        # Check all black cells in this row
        for j in black_rows[i]:
            found = False
            for (l, r) in merged:
                if l <= j <= r:
                    found = True
                    break
            if not found:
                ok = False
                break
        if not ok:
            break

    if ok:
        ans = mid
        low = mid + 1
    else:
        high = mid - 1

print(ans)
0