結果
問題 | No.2039 Copy and Avoid |
ユーザー |
![]() |
提出日時 | 2022-08-12 22:43:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 171 ms / 2,000 ms |
コード長 | 830 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 67,328 KB |
最終ジャッジ日時 | 2024-09-23 03:22:59 |
合計ジャッジ時間 | 3,176 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 31 |
ソースコード
def devisors(n): d = [] a = 1 while a * a < n: if n % a == 0: d.append(a) d.append(n // a) a += 1 if a * a == n: d.append(a) return d INF = 10 ** 18 n, m, a, b = map(int, input().split()) c = list(map(int, input().split())) c.sort() dv = devisors(n) dv.sort() k = len(dv) dp = [INF] * k dp[0] = 0 prv = [-1] * k for i in range(k): x = INF for j in range(m): if c[j] % dv[i] == 0: x = c[j] break for j in range(i + 1, k): if dv[j] % dv[i] > 0: continue if dv[j] >= x: break if dp[j] > dp[i] + a * (dv[j] // dv[i] - 1) + b: dp[j] = dp[i] + a * (dv[j] // dv[i] - 1) + b prv[j] = dv[i] if dp[-1] > 10 ** 15: print(-1) else: print(dp[-1] - b)