Олимпиадный тренинг

Задача . Fuel Economy


Задача

Темы: Жадный алгоритм

Фермер Джон решил в отпуске проехать через всю страну. Чтобы коровы не скучали, он решил арендовать огромный грузовик и взять коров с собой.
Грузовик имеет огромный бензобак, который может вместить до G (1 <= G <= 1,000,000) единиц топлива. Грузовик потребляет одну единицу топлива на одну единицу расстояния. ФД собирается проехать D (1 <= D <= 1,000,000,000) единиц расстояния.
ФД знает, что ему придется несколько раз останавливаться для дозаправки, поэтому он составил список всех N (1 <= N <= 50,000) заправочных станций вдоль маршрута. Для каждой станции i он записал ее расстояние Xi (0 <= Xi <= D) от начала маршрута, а также цену Yi (1 <= Yi <= 1,000,000) заправки единицы топлива на этой станции.
По заданной информации и тому факту, что ФД начинает свое путешествие имея ровно B (0 <= B <= D) единиц топлива, определите минимальное количество денег, которое он должен заплатить за дозаправки топливом чтобы достичь точки назначения. Если достичь точки назначения невозможно, выведите -1. Заметим, что ответ на задачу может не помещаться в стандартное 32-битное целое.
PROBLEM NAME: fuel
Формат входных данных
* Строка 1: Четыре разделенных пробелом целых числа: N, G, B, D.
* Строки 2..1+N: Каждая строка содержит два целых числа Xi и Yi , описывающих заправочную станцию i.
Формат выходных данных
* Строка 1: Минимальная цена, которую ФД должен заплатить, чтобы доехать до места назначения или -1, если доехать невозможно.
Примечание
ФД проезжает 2 единицы расстояния и останавливается, чтобы заправить 2 единицы топлива (цена 40*2), это позволяет доехать ему до станции в позиции 5, где он заправляет полный бак (цена 7*10). Когда он доезжает до позиции 10, он добавляет еще 2 единицы топлива (цена 12*2). Общая цена равна 174.
Примеры
№Входные данныеВыходные данные
1 
4 10 3 17
2 40
9 15
5 7
10 12
 
174
Статистика успешных решений по компиляторам
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет