結果

問題 No.2039 Copy and Avoid
コンテスト
ユーザー ニックネーム
提出日時 2022-08-12 23:25:33
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 637 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 22,144 KB
最終ジャッジ日時 2024-09-23 04:04:59
合計ジャッジ時間 6,607 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import isqrt
from functools import lru_cache
n, m, a, b = map(int, input().split())
c = sorted(map(int, input().split()))
d = set()
for i in range(1, isqrt(n)+1):
    if n%i == 0: d.add(i); d.add(n//i)
d = sorted(d)
@lru_cache
def main(n):
    if n == 1: return -b
    ans = 10**18
    for v in d:
        if v >= n: break
        if n%v != 0: continue
        flag = True
        for w in c:
            if w > n: break
            if w%v == 0: flag = False; break
        if not flag: continue
        res = main(v)
        if res != -1: ans = min(ans, res+b+(n-v)//v*a)
    return ans if ans != 10**18 else -1
print(main(n))
0