結果

問題 No.2456 Stamp Art
ユーザー lam6er
提出日時 2025-04-16 15:49:02
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,883 bytes
コンパイル時間 366 ms
コンパイル使用メモリ 81,528 KB
実行使用メモリ 848,884 KB
最終ジャッジ日時 2025-04-16 15:51:42
合計ジャッジ時間 20,731 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 TLE * 1 MLE * 4 -- * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

prefix = [[0] * (W + 1) for _ in range(H + 1)]
for i in range(1, H + 1):
    row_sum = 0
    for j in range(1, W + 1):
        row_sum += 1 if grid[i-1][j-1] == '#' else 0
        prefix[i][j] = prefix[i-1][j] + row_sum

black_cells = []
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            black_cells.append((i + 1, j + 1))  # Convert to 1-based indexing

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

def check(k):
    if k == 0:
        return False
    max_a = H - k + 1
    max_b = W - k + 1
    if max_a < 1 or max_b < 1:
        return False
    valid = []
    for a in range(1, max_a + 1):
        for b in range(1, max_b + 1):
            x = a + k - 1
            y = b + k - 1
            total = prefix[x][y] - prefix[a-1][y] - prefix[x][b-1] + prefix[a-1][b-1]
            if total == k * k:
                valid.append((a, b))
    if not valid:
        return False
    diff = [[0] * (W + 2) for _ in range(H + 2)]
    for a, b in valid:
        x_end = a + k - 1
        y_end = b + k - 1
        diff[a][b] += 1
        diff[a][y_end + 1] -= 1
        diff[x_end + 1][b] -= 1
        diff[x_end + 1][y_end + 1] += 1
    # Compute row-wise prefix sums
    for i in range(1, H + 1):
        current = 0
        for j in range(1, W + 1):
            current += diff[i][j]
            diff[i][j] = current
    # Compute column-wise prefix sums
    for j in range(1, W + 1):
        current = 0
        for i in range(1, H + 1):
            current += diff[i][j]
            diff[i][j] = current
    for i, j in black_cells:
        if diff[i][j] == 0:
            return False
    return True

while low <= high:
    mid = (low + high) // 2
    if check(mid):
        ans = mid
        low = mid + 1
    else:
        high = mid - 1

print(ans)
0