結果

問題 No.2456 Stamp Art
ユーザー lam6er
提出日時 2025-04-15 22:06:46
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,670 bytes
コンパイル時間 505 ms
コンパイル使用メモリ 81,872 KB
実行使用メモリ 671,564 KB
最終ジャッジ日時 2025-04-15 22:08:34
合計ジャッジ時間 7,837 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other MLE * 1 -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    H = int(input[idx])
    idx += 1
    W = int(input[idx])
    idx += 1
    grid = []
    for _ in range(H):
        grid.append(input[idx])
        idx += 1

    # Convert grid to 0-based index
    dp = [[0] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
            else:
                dp[i][j] = 0

    # Collect all cells with their DP values
    cells = []
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                cells.append((-dp[i][j], i, j))
    # Sort in decreasing order of DP value
    cells.sort()

    max_s = [[0] * W for _ in range(H)]

    for val, x, y in cells:
        s_val = -val
        if s_val == 0:
            continue
        a = x - s_val + 1
        b = y - s_val + 1
        a = max(a, 0)
        b = max(b, 0)
        for i in range(a, x + 1):
            for j in range(b, y + 1):
                if max_s[i][j] < s_val:
                    max_s[i][j] = s_val

    min_k = float('inf')
    black_count = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j] == '#':
                black_count += 1
                if max_s[i][j] == 0:
                    print(0)
                    return
                if max_s[i][j] < min_k:
                    min_k = max_s[i][j]

    print(min_k if min_k != float('inf') else 0)

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