結果

問題 No.1037 exhausted
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:28:07
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 358 ms / 2,000 ms
コード長 1,362 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 82,176 KB
最終ジャッジ日時 2025-03-31 17:29:28
合計ジャッジ時間 4,339 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, v, l = map(int, input().split())
if n == 0:
    if v >= l:
        print(0)
    else:
        print(-1)
    exit()

stations = [tuple(map(int, input().split())) for _ in range(n)]
prev_x = 0
current_dp = {v: 0}

for x_i, v_i, w_i in stations:
    delta = x_i - prev_x
    new_dp = {}
    for fuel_prev, cost_prev in current_dp.items():
        if fuel_prev < delta:
            continue
        fuel_after = fuel_prev - delta
        # Option 1: Do not use this station
        if fuel_after in new_dp:
            if cost_prev < new_dp[fuel_after]:
                new_dp[fuel_after] = cost_prev
        else:
            new_dp[fuel_after] = cost_prev
        # Option 2: Use this station
        max_add = min(v - fuel_after, v_i)
        new_fuel = fuel_after + max_add
        new_cost = cost_prev + w_i
        if new_fuel > v:
            new_fuel = v
        if new_fuel in new_dp:
            if new_cost < new_dp[new_fuel]:
                new_dp[new_fuel] = new_cost
        else:
            new_dp[new_fuel] = new_cost
    current_dp = new_dp
    prev_x = x_i
    if not current_dp:
        break  # No way to proceed further

delta_end = l - prev_x
min_cost = float('inf')
for fuel, cost in current_dp.items():
    if fuel >= delta_end:
        if cost < min_cost:
            min_cost = cost

print(min_cost if min_cost != float('inf') else -1)
0