結果
問題 | No.1330 Multiply or Divide |
ユーザー |
![]() |
提出日時 | 2021-01-10 00:47:59 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 589 ms / 2,000 ms |
コード長 | 759 bytes |
コンパイル時間 | 507 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 32,760 KB |
最終ジャッジ日時 | 2024-11-19 00:13:12 |
合計ジャッジ時間 | 7,327 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
ソースコード
from collections import dequeINF = 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 = deque([(0, 1)])d = {}d[0] = 1while q:c, x = q.popleft()if 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]q.append((c + 1 + k, x * b[k]))