結果
問題 |
No.2844 Birthday Party Decoration
|
ユーザー |
![]() |
提出日時 | 2024-08-23 21:47:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 934 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,452 KB |
実行使用メモリ | 77,988 KB |
最終ジャッジ日時 | 2024-08-23 21:47:49 |
合計ジャッジ時間 | 1,139 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 4 |
ソースコード
import heapq from heapq import heappop,heappush,heapify from sys import stdin, setrecursionlimit input = stdin.readline readline = stdin.readline T=int(input()) from collections import deque d=deque() for _ in range(T): N,X=map(int, input().split()) C=list(map(int, input().split())) d=deque() d.append((X,0)) for i in range(N): D={};c=C[i] while d: now,s=d.popleft() if now&(1<<c): if now not in D: D[now]=s else: D[now]=min(D[now],s) else: p=((now>>c)<<c)-1 q=((now>>c)+1)<<c if p>0: if p not in D: D[p]=s+abs(now-p) else: D[p]=min(D[p],s+abs(now-p)) if q not in D: D[q]=s+abs(now-q) else: D[q]=min(D[q],s+abs(now-q)) for dd in D: d.append((dd,D[dd])) ans=10**22 for d in D: c=D[d]+abs(X-d) ans=min(ans,c) print(ans)