結果

問題 No.1330 Multiply or Divide
ユーザー terry_u16terry_u16
提出日時 2021-01-08 23:17:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,139 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 82,368 KB
実行使用メモリ 747,168 KB
最終ジャッジ日時 2024-11-16 17:40:10
合計ジャッジ時間 67,432 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 7 WA * 5 TLE * 13 MLE * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import heapq
n, m, p = map(int, input().split())
a = list(map(int, input().split()))
costs = [1] * n
for i in range(len(a)):
while a[i] % p == 0:
a[i] //= p
costs[i] += 1
if all([ai == 1 for ai in a]):
print(-1)
exit()
def create_edges(a, costs):
dic = {}
INF = 1000000000
for i in range(len(a)):
if dic.get(a[i], INF) > costs[i]:
dic[a[i]] = costs[i]
a = []
costs = []
for key in dic.keys():
a.append(key)
costs.append(dic[key])
return a, costs
def dijkstra(a, costs, m):
distances = { 1 : 0 }
queue = [(0, 1)]
heapq.heapify(queue)
INF = 1000000000
while len(queue) > 0:
c, v = heapq.heappop(queue)
if c > distances.get(v, INF):
continue
elif v > m:
return c
for i in range(len(a)):
nxt = v * a[i]
cst = c + costs[i]
if cst < distances.get(nxt, INF):
distances[nxt] = cst
heapq.heappush(queue, (cst, nxt))
return INF
a, costs = create_edges(a, costs)
print(dijkstra(a, costs, m))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0