Вы можете зарегистрироваться и решать эту задачу здесь.
| Ограничение времени: | 1 с |
| Ограничение реального времени: | 5 с |
| Ограничение памяти: | 256M |
Электрик наносит ответный удар
В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!
Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.
Первая строка ввода содержит целое число n (2 ≤ n ≤ 1000). Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от 0 до 105.
Выведите одно число – суммарную длину проводов, необходимых, чтобы устроить Очень Длинное Замыкание. Гарантируется, что существует хотя бы один способ соединения штепселей с розетками без нарушения правил средневекового этикета.
Примеры
| Входные данные | Результат работы |
|
2 1 4 6 8 |
9 |
|
2 1 4 2 5 |
2 |
Видеоразбор решения задачи здесь.