結果

問題 No.2146 2 Pows
ユーザー gew1fw
提出日時 2025-06-12 21:03:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,442 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 81,640 KB
実行使用メモリ 433,936 KB
最終ジャッジ日時 2025-06-12 21:05:03
合計ジャッジ時間 6,037 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 2 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    A = int(data[1])
    B = int(data[2])
    C = int(data[3])
    
    max_t = 60
    pow_mod = [1] * (max_t + 1)
    for t in range(1, max_t + 1):
        pow_mod[t] = (pow_mod[t - 1] * 2) % N
    
    INF = float('inf')
    cost = [ [INF] * (max_t + 1) for _ in range(N) ]
    
    heap = []
    for t in range(max_t + 1):
        r = pow_mod[t]
        c = (A + B) * 1 + C * t
        if c < cost[r][t]:
            cost[r][t] = c
            heapq.heappush(heap, (c, r, t))
    
    while heap:
        current_cost, r, t = heapq.heappop(heap)
        if current_cost > cost[r][t]:
            continue
        for s in range(t + 1, max_t + 1):
            delta_r = pow_mod[s]
            new_r = (r + delta_r) % N
            new_t = s
            added_cost = (A + B) + C * (s - t)
            new_cost = current_cost + added_cost
            if new_cost < cost[new_r][new_t]:
                cost[new_r][new_t] = new_cost
                heapq.heappush(heap, (new_cost, new_r, new_t))
    
    result = [INF] * N
    for k in range(N):
        min_cost = INF
        for t in range(max_t + 1):
            if cost[k][t] < min_cost:
                min_cost = cost[k][t]
        result[k] = min_cost if min_cost != INF else -1
    
    for k in range(N):
        print(result[k])

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