結果
問題 | No.2039 Copy and Avoid |
ユーザー |
👑 |
提出日時 | 2022-08-15 21:10:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 698 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 82,164 KB |
実行使用メモリ | 68,596 KB |
最終ジャッジ日時 | 2024-10-02 09:19:04 |
合計ジャッジ時間 | 3,646 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
n, m, a, b = map(int, input().split()) C = list(map(int, input().split())) C.sort() div = [] for i in range(1, int(n ** 0.5 + 1)): if n % i == 0: div.append(i) if i * i != n: div.append(n // i) div.sort() l = len(div) inf = 1 << 60 mi = [inf] * l for i in range(l): d = div[i] for c in C: if c % d == 0: mi[i] = c break dp = [inf] * l dp[0] = -b for i, d in enumerate(div): x = dp[i] + b for j in range(i + 1, l): if div[j] % d != 0: continue if div[j] >= mi[i]: break dp[j] = min(dp[j], x + a * (div[j] // d - 1)) ans = dp[-1] if ans == inf: ans = -1 print(ans)