結果
問題 |
No.2039 Copy and Avoid
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()