結果

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

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    ptr = 0
    N, K = int(data[ptr]), int(data[ptr + 1])
    ptr += 2

    A = [0] * (N + 1)
    B_list = [[] for _ in range(N + 1)]

    for i in range(1, N + 1):
        A[i] = int(data[ptr])
        M_i = int(data[ptr + 1])
        ptr += 2
        if M_i > 0:
            B = list(map(int, data[ptr:ptr + M_i]))
            B_list[i] = B
            ptr += M_i

    max_holding = [ -float('inf') ] * (N + 2)
    max_not_holding = [0] * (N + 2)
    max_holding[0] = -float('inf')

    for i in range(1, N + 1):
        # Compute exchange_candidate
        exchange_candidate = -float('inf')
        for j in B_list[i]:
            if j < i:
                candidate = max_holding[j] - A[j] + A[i]
                if candidate > exchange_candidate:
                    exchange_candidate = candidate

        # Buy candidate
        buy_candidate = max_not_holding[i - 1]

        # Prev holding candidate
        prev_holding_candidate = max_holding[i - 1]

        # Compute new_max_holding
        new_max_holding = max(prev_holding_candidate, buy_candidate, exchange_candidate)
        new_max_not_holding = max(max_not_holding[i - 1], max_holding[i - 1])

        max_holding[i] = new_max_holding
        max_not_holding[i] = new_max_not_holding

    result = max(max_holding[N], max_not_holding[N])
    print(result)

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