結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-10 00:58:59 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 794 bytes |
コンパイル時間 | 334 ms |
コンパイル使用メモリ | 82,352 KB |
実行使用メモリ | 115,840 KB |
最終ジャッジ日時 | 2024-11-19 01:01:53 |
合計ジャッジ時間 | 4,846 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
from heapq import heappop, heappushINF = 10 ** 20N, M, P, *A = map(int, open(0).read().split())def f(x):c = 0while x % P == 0:c += 1x //= Preturn (x, c)max_A = max(A)if max_A > M:print(1)exit()b = {}for m, c in map(f, A):b.setdefault(c, 0)b[c] = max(b[c], m)t = 1for k in sorted(b):if b[k] <= t:del b[k]else:t = b[k]cs = sorted(b)if len(cs) == 0:print(-1)exit()q = [(0, 1)]d = {}d[0] = 1while q:c, x = heappop(q)if d[c] > x:continueif x * max_A > M:print(c + 1)breakfor k in cs:d.setdefault(c + 1 + k, 0)if x * b[k] > d[c + 1 + k]:d[c + 1 + k] = x * b[k]heappush(q, (c + 1 + k, x * b[k]))