結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-08 22:16:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 195 ms / 2,000 ms |
コード長 | 715 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 82,120 KB |
実行使用メモリ | 108,004 KB |
最終ジャッジ日時 | 2025-06-20 01:22:01 |
合計ジャッジ時間 | 5,321 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 51 |
ソースコード
def main(n,m,p,a): ma0=max(a) if ma0>m:return 1 b=[1]*n for i in range(n): while a[i]%p==0: a[i]//=p b[i]+=1 ma1=max(a) if ma1==1: print(-1) exit() ary=[0]*50 for i in range(n): ary[b[i]]=max(ary[b[i]],a[i]) ary=[[i,v] for i,v in enumerate(ary) if v!=0] from heapq import heappush,heappop todo=[[0,1]] inf=float('inf') seen=[0]*1000 seen[0]=1 # seen[i]:操作回数i回における最大 while todo: i,v=heappop(todo) if v*ma0>m:return i+1 for di,dv in ary: if i+di<1000 and seen[i+di]<v*dv: seen[i+di]=v*dv heappush(todo,[i+di,v*dv]) n,m,p=map(int,input().split()) a=list(map(int,input().split())) print(main(n,m,p,a))