Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2458. Задача торговца
Предрасчеты, кэширование вычисленийОлимпиадные задачи на русском языке
| 20/10/2019 | Личное первенство ИЕТН по спортивному программированию (H) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Вдоль длинной дороги расположены несколько городов, пронумерованных от 1 до `n`.
В каждом городе можно купить или продать некоторый товар. Этот товар имеет большой размер,
поэтому торговец может везти с собой не более одной единицы товара. В `i`-м городе товар можно купить
за `p_i` золотых, а продать за `(p_i\ -\ 1)` золотых.
Определите максимальную прибыль, которую может получить торговец при путешествии из города `s` в город `t`.
Первая строка ввода содержит одно целое число `n` (`2\ ≤\ n\ ≤\ 10^6`) – количество городов.
Вторая строка ввода содержит `n` целых чисел `p_i` в диапазоне от 1 до `10^6` – цена товара в каждом городе.
Третья строка ввода содержит одно целое число `m` (`1\ ≤\ m\ ≤\ 10^5`) – количество запросов на вычисление прибыли.
Далее следует `n` строк, содержащих по два целых числа `s` и `t` (`1\ ≤\ s,\ t\ ≤\ n`, `s\ ≠\ t`) – номера
начального и конечного города путешествия.
Для каждого запроса вывести на соответствующей строке одно целое число – максимальную прибыль, которую может получить торговец
при путешествии из города `s` в город `t`.
Пример ввода
7 1 2 7 5 3 10 9 3 1 7 4 7 7 1
Пример вывода
11 6 3
