結果
問題 | No.2456 Stamp Art |
ユーザー | mymelochan |
提出日時 | 2023-09-03 03:05:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,385 ms / 5,000 ms |
コード長 | 1,669 bytes |
コンパイル時間 | 366 ms |
コンパイル使用メモリ | 87,168 KB |
実行使用メモリ | 377,956 KB |
最終ジャッジ日時 | 2023-09-03 03:06:28 |
合計ジャッジ時間 | 27,827 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 80 ms
71,596 KB |
testcase_01 | AC | 79 ms
71,596 KB |
testcase_02 | AC | 81 ms
71,604 KB |
testcase_03 | AC | 1,169 ms
356,860 KB |
testcase_04 | AC | 81 ms
71,612 KB |
testcase_05 | AC | 106 ms
77,536 KB |
testcase_06 | AC | 1,370 ms
377,904 KB |
testcase_07 | AC | 1,245 ms
347,532 KB |
testcase_08 | AC | 1,081 ms
326,920 KB |
testcase_09 | AC | 1,372 ms
366,352 KB |
testcase_10 | AC | 2,168 ms
328,728 KB |
testcase_11 | AC | 1,372 ms
377,956 KB |
testcase_12 | AC | 1,433 ms
334,308 KB |
testcase_13 | AC | 2,249 ms
348,320 KB |
testcase_14 | AC | 2,385 ms
344,852 KB |
testcase_15 | AC | 1,252 ms
352,940 KB |
testcase_16 | AC | 831 ms
234,300 KB |
testcase_17 | AC | 100 ms
78,236 KB |
testcase_18 | AC | 87 ms
77,048 KB |
testcase_19 | AC | 821 ms
318,412 KB |
testcase_20 | AC | 1,782 ms
334,396 KB |
testcase_21 | AC | 1,551 ms
337,936 KB |
testcase_22 | AC | 1,666 ms
328,296 KB |
testcase_23 | AC | 178 ms
86,356 KB |
testcase_24 | AC | 296 ms
89,452 KB |
testcase_25 | AC | 87 ms
71,980 KB |
ソースコード
############################################################# import sys sys.setrecursionlimit(10**7) from heapq import heappop,heappush from collections import deque,defaultdict,Counter from bisect import bisect_left, bisect_right from itertools import product,combinations,permutations ipt = sys.stdin.readline def iin(): return int(ipt()) def lmin(): return list(map(int,ipt().split())) MOD = 998244353 ############################################################# N,M = lmin() S = [input() for _ in range(N)] S = [[0 if S[i][j] == "." else 1 for j in range(M)] for i in range(N)] T = [[0]*(M+1) for _ in range(N+1)] for i in range(N): for j in range(M): T[i+1][j+1] = T[i][j+1]+T[i+1][j]-T[i][j]+S[i][j] def check(x): cnt = [[0]*(M+2) for _ in range(N+2)] for i in range(N-x+1): for j in range(M-x+1): #print(i,j,T[i+x+1][j+x+1]-T[i][j+x+1]-T[i+x+1][j]+T[i][j]) if T[i+x][j+x]-T[i][j+x]-T[i+x][j]+T[i][j] == x**2: cnt[i+1][j+1] += 1 cnt[i+1][j+x+1] -= 1 cnt[i+x+1][j+1] -= 1 cnt[i+x+1][j+x+1] += 1 #print(cnt) for i in range(1,N+1): for j in range(1,M+1): cnt[i][j] += cnt[i][j-1] for i in range(1,N+1): for j in range(1,M+1): cnt[i][j] += cnt[i-1][j] #print(x,cnt) for i in range(1,N+1): for j in range(1,M+1): if S[i-1][j-1] and not cnt[i][j]: return False return True ok = 1 ng = min(N,M)+1 while ng-ok > 1: cen = (ok+ng)//2 if check(cen): ok = cen else: ng = cen print(ok)