Tại mỗi trạm xăng hiện tại, bạn nhìn về phía trước trong tầm đi được tối đa C km.
Trường hợp 1: Nếu có trạm xăng nào giá rẻ hơn trạm hiện tại, bạn chỉ đổ vừa đủ xăng để đi đến trạm rẻ hơn gần nhất đó.
Trường hợp 2: Nếu không có trạm nào rẻ hơn, trạm hiện tại là rẻ nhất trong vùng, bạn hãy đổ đầy bình xăng để tận dụng giá rẻ, sau đó đi đến trạm tiếp theo.
Nếu khoảng cách giữa hai trạm kế tiếp lớn hơn C km thì xe không thể đến đích, kết quả sẽ là -1. Chúng ta coi điểm đích B là một trạm xăng ở vị trí d với giá bằng 0.Dưới đây là mã nguồn Python toàn bộ bằng chữ thường và văn bản thuần túy không định dạng:import sysdef solve():
input_data = sys.stdin.read().split()
if not input_data:
returnn = int(input_data[0])
d = int(input_data[1])
C = int(input_data[2])stations = []
idx = 3
for _ in range(n):
x = int(input_data[idx])
p = int(input_data[idx+1])
stations.append((x, p))
idx += 2stations.sort(key=lambda s: s[0])
stations.append((d, 0))if stations[0][0] > 0:
print(-1)
returnfor i in range(len(stations) - 1):
if stations[i+1][0] - stations[i][0] > C:
print(-1)
returntotal_cost = 0
current_fuel = 0
i = 0
num_stations = len(stations)while i < num_stations - 1:
curr_x, curr_p = stations[i]
next_cheaper_idx = -1for j in range(i + 1, num_stations):
if stations[j][0] - curr_x <= C:
if stations[j][1] < curr_p:
next_cheaper_idx = j
break
else:
breakif next_cheaper_idx != -1:
dist_needed = stations[next_cheaper_idx][0] - curr_x
fuel_to_buy = max(0, dist_needed - current_fuel)
total_cost += fuel_to_buy * curr_p
current_fuel = current_fuel + fuel_to_buy - dist_needed
i = next_cheaper_idx
else:
fuel_to_buy = C - current_fuel
total_cost += fuel_to_buy * curr_p
dist_to_next = stations[i+1][0] - curr_x
current_fuel = C - dist_to_next
i += 1print(total_cost)if name == 'main':
solve()