結果

問題 No.2456 Stamp Art
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 12:53:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,024 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 119,552 KB
最終ジャッジ日時 2025-06-12 12:56:08
合計ジャッジ時間 10,105 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

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)
    
    # Precompute prefix sums
    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
    
    # Function to calculate sum of a rectangle (a, b) to (c, d)
    def get_sum(a, b, c, d):
        return prefix[c][d] - prefix[a-1][d] - prefix[c][b-1] + prefix[a-1][b-1]
    
    min_k = float('inf')
    for i in range(1, H+1):
        for j in range(1, W+1):
            if grid[i-1][j-1] != '#':
                continue
            low = 1
            high = min(H, W)
            best = 0
            while low <= high:
                mid = (low + high) // 2
                a_min = max(1, i - mid + 1)
                a_max = min(H - mid + 1, i)
                b_min = max(1, j - mid + 1)
                b_max = min(W - mid + 1, j)
                found = False
                # Check if any square of size mid covers (i,j)
                for a in range(a_min, a_max + 1):
                    for b in range(b_min, b_max + 1):
                        c = a + mid - 1
                        d = b + mid - 1
                        if c > H or d > W:
                            continue
                        total = get_sum(a, b, c, d)
                        if total == mid * mid:
                            found = True
                            break
                    if found:
                        break
                if found:
                    best = mid
                    low = mid + 1
                else:
                    high = mid - 1
            if best == 0:
                print(0)
                return
            if best < min_k:
                min_k = best
    print(min_k)

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