結果
問題 | No.1330 Multiply or Divide |
ユーザー |
👑 ![]() |
提出日時 | 2021-01-08 22:16:21 |
言語 | PyPy3 (7.3.15) |
結果 |
MLE
|
実行時間 | - |
コード長 | 643 bytes |
コンパイル時間 | 600 ms |
コンパイル使用メモリ | 81,948 KB |
実行使用メモリ | 846,644 KB |
最終ジャッジ日時 | 2024-11-16 12:45:03 |
合計ジャッジ時間 | 70,259 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 WA * 2 TLE * 13 MLE * 21 |
ソースコード
#================================================from functools import lru_cacheimport sys,heapqinput=sys.stdin.readlineN,M,P=map(int,input().split())A=list(set(map(int,input().split())))D={}for a in A:b=am=1while a%P==0:a//=Pm+=1D[b]=(m,a)if not D:print(-1)exit(0)T={1:0}Q=[(0,1)]heapq.heapify(Q)X=float("inf")while Q:d,x=heapq.heappop(Q)if x>M or d>T[x]:continuefor b in D:m,a=D[b]if x*b>M:X=min(X,T[x]+1)if a>1 and (x*a not in T) or T[x*a]>d+m:T[x*a]=d+mQ.append((d+m,x*a))print(X)