結果
問題 |
No.1037 exhausted
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)