結果
問題 | No.2456 Stamp Art |
ユーザー | detteiuu |
提出日時 | 2024-12-22 07:28:00 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,699 bytes |
コンパイル時間 | 361 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 680,640 KB |
最終ジャッジ日時 | 2024-12-22 07:29:02 |
合計ジャッジ時間 | 58,071 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
53,044 KB |
testcase_01 | AC | 40 ms
52,900 KB |
testcase_02 | AC | 65 ms
52,992 KB |
testcase_03 | MLE | - |
testcase_04 | AC | 41 ms
54,112 KB |
testcase_05 | AC | 58 ms
67,072 KB |
testcase_06 | MLE | - |
testcase_07 | MLE | - |
testcase_08 | MLE | - |
testcase_09 | MLE | - |
testcase_10 | MLE | - |
testcase_11 | MLE | - |
testcase_12 | MLE | - |
testcase_13 | MLE | - |
testcase_14 | MLE | - |
testcase_15 | MLE | - |
testcase_16 | AC | 1,862 ms
358,052 KB |
testcase_17 | AC | 68 ms
69,388 KB |
testcase_18 | AC | 49 ms
61,620 KB |
testcase_19 | AC | 2,226 ms
489,724 KB |
testcase_20 | MLE | - |
testcase_21 | MLE | - |
testcase_22 | MLE | - |
testcase_23 | AC | 226 ms
94,160 KB |
testcase_24 | AC | 388 ms
119,496 KB |
testcase_25 | AC | 40 ms
53,264 KB |
ソースコード
class cum2:def __init__(self, A):self.cum = [[0]*(len(A[0])+1) for _ in range(len(A)+1)]for i in range(len(A)):for j in range(len(A[0])):self.cum[i+1][j+1] = A[i][j]for i in range(1, len(A)+1):for j in range(2, len(A[0])+1):self.cum[i][j] += self.cum[i][j-1]for i in range(2, len(A)+1):for j in range(1, len(A[0])+1):self.cum[i][j] += self.cum[i-1][j]def query(self, lh, lw, rh, rw):return self.cum[rh+1][rw+1]+self.cum[lh][lw]-self.cum[rh+1][lw]-self.cum[lh][rw+1]H, W = map(int, input().split())S = [list(input()) for _ in range(H)]def func(n):imos = [[0]*(W+1) for _ in range(H+1)]for i in range(H-n+1):for j in range(W-n+1):if cum.query(i, j, i+n-1, j+n-1) == n**2:imos[i][j] += 1imos[i+n][j+n] += 1imos[i][j+n] -= 1imos[i+n][j] -= 1for i in range(H+1):for j in range(1, W+1):imos[i][j] += imos[i][j-1]for i in range(1, H+1):for j in range(W+1):imos[i][j] += imos[i-1][j]imos.pop()for i in range(H):for j in range(W):if 1 <= imos[i][j]:imos[i][j] = "#"else:imos[i][j] = "."imos[i].pop()return imos == SC = [[0]*W for _ in range(H)]for i in range(H):for j in range(W):if S[i][j] == "#":C[i][j] = 1cum = cum2(C)left = 1right = min(H, W)+1while left+1 < right:mid = (left+right)//2if func(mid):left = midelse:right = midprint(left)