結果

問題 No.2039 Copy and Avoid
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:17:07
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,615 bytes
コンパイル時間 324 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 866,308 KB
最終ジャッジ日時 2025-06-12 20:18:53
合計ジャッジ時間 7,669 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    N, M, A, B = map(int, sys.stdin.readline().split())
    C = list(map(int, sys.stdin.readline().split()))
    forbidden = set(C)
    
    if N in forbidden:
        print(-1)
        return
    
    heap = []
    heapq.heappush(heap, (0, 1))
    visited = {}
    
    while heap:
        cost, y = heapq.heappop(heap)
        if y in visited:
            if visited[y] <= cost:
                continue
        visited[y] = cost
        if y == N:
            print(cost)
            return
        
        t_max = N // y
        if t_max < 2:
            continue
        
        forbidden_t = []
        for c in C:
            if c % y == 0:
                t = c // y
                if t >= 2:
                    forbidden_t.append(t)
        forbidden_t.sort()
        
        if forbidden_t:
            first_forbidden = forbidden_t[0]
            max_t = min(first_forbidden - 1, t_max)
        else:
            max_t = t_max
        
        ki_max = max_t - 1
        if ki_max < 1:
            continue
        
        for ki in range(1, ki_max + 1):
            new_x = y * (ki + 1)
            if new_x > N:
                continue
            new_cost = cost + ki * A
            if new_x == N:
                print(new_cost)
                return
            else:
                new_y = new_x
                new_cost_b = new_cost + B
                if new_y not in visited or visited.get(new_y, float('inf')) > new_cost_b:
                    heapq.heappush(heap, (new_cost_b, new_y))
    
    print(-1)

if __name__ == "__main__":
    main()
0