結果

問題 No.2146 2 Pows
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:01:20
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,557 bytes
コンパイル時間 399 ms
コンパイル使用メモリ 82,284 KB
実行使用メモリ 222,952 KB
最終ジャッジ日時 2025-04-15 23:02:20
合計ジャッジ時間 5,371 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 2 TLE * 1 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, A, B, C = map(int, sys.stdin.readline().split())
    max_e = 40  # Adjust this based on the problem's needs
    
    # Precompute pow2 mod N for exponents up to max_e
    pow2 = [1] * (max_e + 1)
    for e in range(1, max_e + 1):
        pow2[e] = (pow2[e-1] * 2) % N
    
    # Precompute min_k for each e using BFS
    min_k = [ [ -1 for _ in range(N) ] for _ in range(max_e + 1) ]
    for e in range(max_e + 1):
        a = pow2[e]
        q = deque()
        q.append(0)
        dist = [ -1 ] * N
        dist[0] = 0
        while q:
            current = q.popleft()
            next_sum = (current + a) % N
            if dist[next_sum] == -1:
                dist[next_sum] = dist[current] + 1
                q.append(next_sum)
        for r in range(N):
            min_k[e][r] = dist[r]
    
    # Initialize answer and best_prev_cost
    ans = [float('inf')] * N
    best_prev_cost = [float('inf')] * N
    
    for e in range(max_e + 1):
        current_dp = [float('inf')] * N
        
        # Step a: add elements of e to sum 0
        for r in range(N):
            k = min_k[e][r]
            if k >= 1:
                cost = A * k + B + C * e
                if cost < current_dp[r]:
                    current_dp[r] = cost
        
        # Step b: add elements of e to previous sums
        # Precompute residues for e where min_k[e][r] >=1
        residues = []
        for r in range(N):
            if min_k[e][r] >= 1:
                residues.append(r)
        
        for s_prev in range(N):
            if best_prev_cost[s_prev] == float('inf'):
                continue
            for r in residues:
                s = (s_prev + r) % N
                k = min_k[e][r]
                cost = best_prev_cost[s_prev] + A * k + B + C * e
                if cost < current_dp[s]:
                    current_dp[s] = cost
        
        # Update ans
        for s in range(N):
            if current_dp[s] < ans[s]:
                ans[s] = current_dp[s]
        
        # Update best_prev_cost
        for s in range(N):
            if current_dp[s] != float('inf'):
                candidate = current_dp[s] - C * e
                if candidate < best_prev_cost[s]:
                    best_prev_cost[s] = candidate
    
    # Handle the case where no set is found (though problem states S is non-empty)
    for k in range(N):
        if ans[k] == float('inf'):
            print(-1)
        else:
            print(ans[k])

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