10/04/2025 23:08:22

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2598. Экспедиция

Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В некоторых точках длинной прямой дороги, идущей через пустыню, расположены посадочные площадки. Известны расстояния от начала дороги до каждой из площадок. Несколько экспедиций хотят добраться до разных точек на дороге. Для этого каждая экспедиция должна сначала высадиться на одной из площадок (не обязательно ближайшей к нужной точке), затратив на это определенное количество топлива для вертолета, а затем проехать от площадки до нужной точки по дороге, затратив дополнительное топливо на каждую единицу пути.

Напишите программу, которая рассчитает для каждой экспедиции, какое минимальное количество топливо необходимо для доставки экспедиции в заданную точку.

В первой строке ввода содержатся три целых числа: количество площадок $N$ ( $1 <= N <= 10^5$ ), количество экспедиций $M$ ( $1 <= M <= 10^5$ ) и затраты топлива на проезд одной единицы дороги $C$ ( $1 <= C <= 10^9$ ). Далее следует $N$ строк, содержащих по два целых числа: расстояние от начала дороги до $i$ -й площадки $A_i$ ( $0 <= A_i <= 10^9$ ) и затраты топлива для доставки экспедиции на $i$ -ю площадку $B_i$ ( $1 <= B_i <= 10^9$ ). Все площадки расположены в разных точках дороги. Далее следует $M$ строк, содержащих одно целое числа: расстояние от начала дороги до цели $j$ -й экспедиции $D_j$ ( $0 <= D_j <= 10^9$ ).

Для каждой экспедиции вывести одно целое число на отдельной строке – минимальное количество топлива для доставки экспедиции в заданную точку.

Пример ввода

Пример вывода

250
260

Пояснение к примеру: первая экспедиция высаживается на второй площадке (на расстоянии 300 от начала дороги), затратив 100 единиц топлива, а затем проезжает до точки 150, затратив еще 150 единиц топлива. Вторая экспедиция высаживается на третьей площадке (на расстоянии 100 от начала дороги), затратив 250 единиц топлива, а затем проезжает до точки 110, затратив еще 10 единиц топлива.

Система оценки и описание подзадач

Подзадача 1 (30 баллов)

$N = 1$ , $M = 1$

В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 2 (40 баллов)

$1 < N <= 1000$ , $1 < M <= 1000$

Необходимые подзадачи: 1.

В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

Подзадача 3 (30 баллов)

$1000 < N <= 100000$ , $1000 < M <= 100000$

Необходимые подзадачи: 1, 2.

В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

19/11/2021	Муниципальный этап 9 класс (5)
30/06/2023	Лето 2023-3 сложные (командное) (H)
13/11/2023	Сканирующая прямая (проводит BOGAT) (F)
28/06/2024	Лето 2024-3 сложные (командное) (H)
06/11/2024	ЦОП1 (дорешивание) Метод сканирующей прямой (проводит BOGAT) (E)