結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2024-08-16 22:24:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 659 ms / 2,000 ms |
コード長 | 622 bytes |
コンパイル時間 | 390 ms |
コンパイル使用メモリ | 82,108 KB |
実行使用メモリ | 80,360 KB |
最終ジャッジ日時 | 2024-08-16 22:24:54 |
合計ジャッジ時間 | 10,009 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
n,K=map(int,input().split())sx,sy,gx,gy=map(int,input().split())sx,sy=sx+sy,sx-sygx,gy=gx+gy,gx-gyp=[(sx,sy)]for i in range(n):x,y=map(int,input().split())p+=[(x+y,x-y)]p+=[(gx,gy)]n+=2ok=10**6ng=0from heapq import heappush,heappopwhile ok-ng>1:m=(ok+ng)//2X=1<<60v=[X]*nv[0]=0q=[(v[0],0)]while len(q)>0:sc,sp=heappop(q)sx,sy=p[sp]if sc>v[sp]:continuefor tp in range(n):tx,ty=p[tp]tc=max(max(abs(tx-sx),abs(ty-sy))-1,0)//mif v[tp]>sc+tc:v[tp]=sc+tcheappush(q,(v[tp],tp))if v[-1]<=K:ok=melse:ng=mprint(ok)