Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
832. Доставка
Олимпиадные задачи на русском языке| 17/03/2008 | Школьные сборы, дорешивание (1D) |
| 17/03/2008 | Школьные сборы, день 1 (D) |
Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Город Прямой Рог представляет собой одну прямую улицу. В городе работает компания, которая занимается доставкой товаров.
Для удобства, адреса доставки представлены в виде чисел, которые задают расстояние от офиса компании.
Положительные числа в одну сторону, а отрицательные – в другую. Заказы на доставку выполняются компанией
последовательно, в том порядке, в котором они были заданы.
В компании работает два курьера. В начале рабочего дня заказы распределяются между ними, и каждый отправляется
по своему маршруту. Компании необходимо так спланировать распределение заказов, чтобы суммарное расстояние,
которое будет пройдено курьерами на момент выполнения последнего заказа, была минимальным.
Напишите программу, которая по расстояниям адресатов от офиса компании находит наименьшее суммарное расстояние,
которое пройдут ее работники.
Первая строка входного файла содержит целое число `N` (`1\ ≤\ N\ ≤\ 100\ 000`) – количество заказов. Далее следует `N` строк,
каждая из которых содержит одно целое число – расстояние от офиса до адресата. Если расстояние положительное –
то адресат находится в одной части города относительно офиса компании, а если отрицательное, то в другой.
Расстояния по модулю не превышают `10^8`.
Единственная строка выходного файла должна содержать одно целое число – минимально возможное суммарное расстояние,
которое пройдут оба работника компании.
Пример ввода
5 1 -1 2 -2 3
Пример вывода
5
