結果

問題 No.1676 Coin Trade (Single)
コンテスト
ユーザー lam6er
提出日時 2025-03-26 15:56:16
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 1,441 bytes
コンパイル時間 192 ms
コンパイル使用メモリ 82,748 KB
実行使用メモリ 116,552 KB
最終ジャッジ日時 2025-03-26 15:56:47
合計ジャッジ時間 5,576 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, K = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    
    A = []
    B = []
    for _ in range(N):
        Ai = int(input[ptr])
        Mi = int(input[ptr+1])
        ptr += 2
        Bi = list(map(int, input[ptr:ptr+Mi])) if Mi > 0 else []
        ptr += Mi
        A.append(Ai)
        B.append(Bi)
    
    cash = [-float('inf')] * (N + 1)
    hold = [-float('inf')] * (N + 1)
    cash[0] = 0  # Initial state: no coins
    
    for i in range(1, N+1):
        Ai = A[i-1]
        Bi = B[i-1]
        
        max_val = -float('inf')
        for j in Bi:
            j_idx = j  # j is 1-based in input, converted to 0-based in the list
            current_val = hold[j_idx] - A[j_idx-1]  # j is 1-based in input
            if current_val > max_val:
                max_val = current_val
        
        new_hold_candidate = -float('inf')
        if Bi:
            new_hold_candidate = max_val + Ai
        
        # Compute new_hold
        prev_hold = hold[i-1]
        prev_cash = cash[i-1]
        new_hold = max(prev_hold, prev_cash)
        if new_hold_candidate != -float('inf'):
            new_hold = max(new_hold, new_hold_candidate)
        
        # Compute new_cash
        new_cash = max(prev_cash, new_hold)
        
        cash[i] = new_cash
        hold[i] = new_hold
    
    print(cash[N])

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