結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-10 01:05:47 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 786 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 82,380 KB |
実行使用メモリ | 115,716 KB |
最終ジャッジ日時 | 2024-11-19 01:24:58 |
合計ジャッジ時間 | 5,271 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
from heapq import heappop, heappushN, 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]if len(b) == 0:print(-1)exit()q = [(0, 1)]max_x = {}max_x[0] = 1while q:c, x = heappop(q)if max_x[c] > x:continueif x * max_A > M:print(c + 1)breakfor k in b:nc = c + 1 + knx = x * b[k]max_x.setdefault(nc, 0)if nx > max_x[nc]:max_x[nc] = nxheappush(q, (nc, nx))