結果
問題 |
No.1037 exhausted
|
ユーザー |
![]() |
提出日時 | 2025-03-26 15:46:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 241 ms / 2,000 ms |
コード長 | 1,624 bytes |
コンパイル時間 | 159 ms |
コンパイル使用メモリ | 82,360 KB |
実行使用メモリ | 78,168 KB |
最終ジャッジ日時 | 2025-03-26 15:47:26 |
合計ジャッジ時間 | 3,607 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
import sys import math def main(): N, V, L = map(int, sys.stdin.readline().split()) stations = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)] if L <= V: print(0) return if N == 0: print(-1) return x0, v0, w0 = stations[0] if x0 > V: print(-1) return initial_fuel = V - x0 INF = math.inf prev_dp = [INF] * (V + 1) prev_dp[initial_fuel] = 0 # No refill new_fuel = min(initial_fuel + v0, V) if prev_dp[new_fuel] > w0: prev_dp[new_fuel] = w0 prev_x = x0 for i in range(1, N): x_i, v_i, w_i = stations[i] distance = x_i - prev_x curr_dp = [INF] * (V + 1) for fuel_prev in range(V + 1): if prev_dp[fuel_prev] == INF: continue if fuel_prev < distance: continue fuel_after_move = fuel_prev - distance # Without refilling if curr_dp[fuel_after_move] > prev_dp[fuel_prev]: curr_dp[fuel_after_move] = prev_dp[fuel_prev] # With refilling new_f = min(fuel_after_move + v_i, V) new_cost = prev_dp[fuel_prev] + w_i if curr_dp[new_f] > new_cost: curr_dp[new_f] = new_cost prev_dp = curr_dp prev_x = x_i required = L - prev_x min_cost = INF for fuel in range(required, V + 1): if prev_dp[fuel] < min_cost: min_cost = prev_dp[fuel] print(min_cost if min_cost != INF else -1) if __name__ == "__main__": main()