結果

問題 No.2146 2 Pows
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:11:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,928 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 388,180 KB
最終ジャッジ日時 2025-06-12 16:11:23
合計ジャッジ時間 5,395 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 3 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    N, A, B, C = map(int, sys.stdin.readline().split())
    
    max_z = 30  # Since 2^30 is sufficient for N up to 2e5
    pow_mod = [(1 << i) % N for i in range(max_z + 1)]
    
    # Initialize DP: dp[r][z] = minimal cost
    INF = float('inf')
    dp = [ [INF] * (max_z + 1) for _ in range(N) ]
    
    heap = []
    for i in range(max_z + 1):
        r = pow_mod[i]
        cost = A * 1 + B * 1 + C * i
        if dp[r][i] > cost:
            dp[r][i] = cost
            heapq.heappush(heap, (cost, r, i, 1))
    
    while heap:
        cost, r, z, y = heapq.heappop(heap)
        if cost > dp[r][z]:
            continue
        for i in range(max_z + 1):
            add_mod = pow_mod[i]
            new_r = (r + add_mod) % N
            new_z = max(z, i)
            if i > z:
                new_y = y + 1
                delta = A + B + C * (i - z)
            else:
                new_y = y
                if i <= z:
                    if i == z:
                        delta = A
                    else:
                        # Check if i is already in the used powers
                        # Since we can't track that, assume it's not
                        # This is an approximation
                        delta = A + B
                        new_y += 1
                else:
                    delta = A + B + C * (i - z)
                    new_z = i
                    new_y += 1
            new_cost = cost + delta
            if new_cost < dp[new_r][new_z]:
                dp[new_r][new_z] = new_cost
                heapq.heappush(heap, (new_cost, new_r, new_z, new_y))
    
    result = [INF] * N
    for r in range(N):
        for z in range(max_z + 1):
            if dp[r][z] < result[r]:
                result[r] = dp[r][z]
    
    for r in range(N):
        print(result[r] if result[r] != INF else -1)

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