Задача №114526. Превышение скорости
Превышение скорости является опасным нарушением, значительно увеличивающим вероятность трагических последствий транспортных происшествий. К сожалению контроль скорости с использованием радаров и камер не решает проблему полностью. Притормаживая перед камерами, водители едут со значительным превышением на участках дорог, где контроль не ведётся. С целью предотвращения такого поведения используется назначение штрафа за гарантирование превышение скорости, основанное на времени проезда дороги.
Рассмотрим дорогу, состоящую из \(n\) участков, пронумерованных от \(1\) до \(n\). Длина \(i\)-го участка составляет \(l_i\) метров. На \(i\)-м из участков установлено ограничение по скорости в \(v_i\) м/с.
За превышение скорости предусмотрены штрафы. В зависимости от превышения, установлены различные штрафы, величина штрафа вычисляется следующим образом.
Пусть \(e\) — максимальное превышение разрешённой скорости в процессе пребывания автомобиля на всей дороге, то есть максимальная разница между скоростью автомобиля и максимальной разрешенной скоростью на участке, где он в этот момент находится. Если превышения скорости не было, то штраф не взимается. В противном случае штраф вычисляется так:
- если \(0 \lt e \le a_1\), то штраф составляет \(f_1\) денежных единиц;
- если \(a_1 \lt e \le a_2\), то штраф составляет \(f_2\) денежных единиц;
- \(\ldots\)
- если \(a_{m - 2} \lt e \le a_{m-1}\), то штраф составляет \(f_{m-1}\) денежных единиц;
- если \(a_{m-1} \lt e\), то штраф составляет \(f_{m}\) денежных единиц.
Автоматическая система назначения штрафов получила данные о \(q\) автомобилях. Для удобства пронумеруем их от \(1\) до \(q\). Известно, что \(i\)-й автомобиль заехал на дорогу в момент времени \(s_i\), проехал все \(n\) участков, после чего выехал с нее в момент времени \(t_i\). Отсчёт времени будем вести в секундах с открытия дороги.
Для каждого из автомобилей система должна определить, какой максимальный штраф можно гарантированно выписать этому автомобилю, основываясь только на времени заезда на дорогу и выезда с нее.
Требуется написать программу, которая по описанию границ диапазонов превышения скорости, соответствующих штрафов и временам въезда/выезда автомобилей определяет для каждого автомобиля максимальный штраф, который можно выписать этому автомобилю.
Первая строка входных данных содержит единственное целое число \(n\) — количество участков на дороге (\(1 \le n \le 10\)).
Вторая строка содержит \(n\) целых чисел \(v_i\) — ограничения скорости на участках (\(1 \le v_i \le 10^9\)).
Третья строка содержит \(n\) целых чисел \(l_i\) — длины участков (\(1 \le l_i \le 10^9\)).
Четвертая строка содержит единственное целое число \(m\) — количество границ диапазонов превышения скорости (\(1 \le m \le 10^5\)).
Пятая строка содержит \(m-1\) целых чисел \(a_i\) — границы диапазонов превышения скорости (\(1 \le a_i \le 10^9\)). Гарантируется, что значения \(a_i\) строго возрастают. Обратите внимание, что если \(m = 1\), то пятая строка ввода пустая.
Шестая строка содержит \(m\) целых чисел \(f_i\) — штрафы за диапазоны превышения скоростей (\(1 \le f_i \le 10^9\)). Гарантируется, что значения \(f_i\) возрастают.
Седьмая строка содержит единственное целое число \(q\) — количество автомобилей, которые надо обработать (\(1 \le q \le 10^5\)).
Каждая из следующих \(q\) строк содержит два целых числа \(s_i\) и \(t_i\) — время заезда на трассу и выезда с неё \(i\)-го из рассматриваемых автомобилей (\(1 \le s_i \lt t_i \le 10^9\)).
Для каждого из \(q\) автомобилей выведите в отдельной строке максимальный штраф, который гарантированно можно выписать этому автомобилю, основываясь только на временах его заезда на дорогу и выезда с нее. Если возможна ситуация, что автомобиль ни разу не превысил разрешённую скорость, следует вывести \(0\).
Гарантируется, что если время въезда или выезда автомобиля изменить не более чем на \(10^{-5}\), штраф, который можно ему выписать, не изменится.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 5 | \(n = 1\), \(m = 1\) | первая ошибка | |
| 2 | 10 | \(m = 1\) | 1 | первая ошибка |
| 3 | 9 | \(n = 1\), \(m \le 10\) | 1 | первая ошибка |
| 4 | 12 | \(n = 1\) | 1, 3 | первая ошибка |
| 5 | 13 | \(m \le 10\), \(a_i \le 10\) | первая ошибка | |
| 6 | 14 | \(m \le 10\) | 1, 2, 3, 5 | первая ошибка |
| 7 | 37 | 1 – 6 | первая ошибка |
3 10 20 30 400 500 600 6 1 5 10 12 16 100 300 600 800 1000 1500 3 10 100 20 70 45 100
0 800 600