結果

問題 No.2039 Copy and Avoid
ユーザー lam6er
提出日時 2025-03-31 17:53:05
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,446 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 92,192 KB
最終ジャッジ日時 2025-03-31 17:54:28
合計ジャッジ時間 6,823 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def get_divisors(n):
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return sorted(divisors)

def main():
    sys.setrecursionlimit(1 << 25)
    N, M, A, B = map(int, sys.stdin.readline().split())
    C = list(map(int, sys.stdin.readline().split()))
    forbidden = set(C)
    
    if N == 1:
        print(0)
        return
    
    divisors = get_divisors(N)
    divisors_set = set(divisors)
    add_valid = {}
    
    # Precompute additive validity for each divisor
    for F in divisors:
        if F == 0:
            continue
        k = N // F
        if F * k != N:
            add_valid[F] = False
            continue
        is_valid = True
        for c in forbidden:
            if c % F != 0:
                continue
            m = c // F
            if 2 <= m < k:
                is_valid = False
                break
        add_valid[F] = is_valid
    
    # BFS to find minimal cost for each divisor
    dist = {1: 0}
    queue = deque([1])
    
    while queue:
        P = queue.popleft()
        current_cost = dist[P]
        q = N // P
        if q < 1:
            continue
        
        # Get divisors of q
        divisors_q = get_divisors(q)
        
        for m in divisors_q:
            new_P = P * m
            if new_P not in divisors_set:
                continue
            # Check if any step is forbidden
            valid = True
            for j in range(2, m + 1):
                if P * j in forbidden:
                    valid = False
                    break
            if not valid:
                continue
            
            new_cost = current_cost + (m - 1) * A + B
            if new_P not in dist or new_cost < dist.get(new_P, float('inf')):
                dist[new_P] = new_cost
                queue.append(new_P)
    
    # Find the minimal total cost
    min_total = float('inf')
    for F in divisors:
        if F not in dist:
            continue
        if not add_valid.get(F, False):
            continue
        k = N // F
        if k == 0:
            continue
        additive_cost = (k - 1) * A
        total_cost = dist[F] + additive_cost
        if total_cost < min_total:
            min_total = total_cost
    
    print(-1 if min_total == float('inf') else min_total)

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