結果
問題 | 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 = 1while a * a < n:if n % a == 0:d.append(a)d.append(n // a)a += 1if a * a == n:d.append(a)return dINF = 10 ** 18n, 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] * kdp[0] = 0prv = [-1] * kfor i in range(k):x = INFfor j in range(m):if c[j] % dv[i] == 0:x = c[j]breakfor j in range(i + 1, k):if dv[j] % dv[i] > 0:continueif dv[j] >= x:breakif dp[j] > dp[i] + a * (dv[j] // dv[i] - 1) + b:dp[j] = dp[i] + a * (dv[j] // dv[i] - 1) + bprv[j] = dv[i]if dp[-1] > 10 ** 15:print(-1)else:print(dp[-1] - b)