Задача №114956. Запись на экзамен
Обычно Новый год у всех ассоциируется с ёлкой и праздничным столом, однако у студентов Новый год ассоциируется с сессией. Наступило 31 декабря, и студенты второго курса записались на сдачу экзамена.
Всего существует \(n\) дней, в которые можно сдавать экзамен. Каждый студент записался для сдачи на один из этих дней. Получилось, что в \(i\)-й день экзамен желают сдать \(a_{i}\) студентов, а максимальное количество студентов, у которых преподаватели готовы принять экзамен в этот день, равно \(b_{i}\).
Преподавателям необходимо обеспечить всем студентам возможность сдавать экзамен, поэтому некоторых студентов может быть придется переместить на другой день. Преподаватели могут выбрать любое множество студентов и назначить каждому из них любой день для сдачи.
Если студент желал сдать экзамен в \(i\)-й день, а преподаватели в итоге перенесли его на \(j\)-й день, то недовольство этого студента будет равно \(|i - j|\).
Помогите преподавателям распределить студентов так, чтобы для всех \(i\) в \(i\)-й день экзамен сдавали не более \(b_i\) студентов, а максимальное недовольство среди студентов было минимальным.
В первой строке ввода дано одно целое число \(n\) — количество дней, в которые можно сдавать экзамен (\(1 \le n \le 10^{6}\)).
Во второй строке ввода даны \(n\) целых чисел \(a_{i}\) — количество студентов, которые желают сдать экзамен в \(i\)-й день (\(1 \le a_i \le 10^{9}\)).
В третьей строке ввода даны \(n\) целых чисел \(b_{i}\) — максимальное количество студентов, у которых преподаватели готовы принять экзамен в \(i\)-й день (\(0 \le b_i \le 10^{9}\)).
Выведите единственное целое число — для какого минимального \(k\) можно добиться, чтобы недовольство любого студента не превышало \(k\). Если решения не существует, следует вывести \(-1\).
Рассмотрим первый пример. Заметим, что 70 студентов хотят сдавать экзамен в третий день, но суммарно во второй, третий и четвертый день сдать экзамен смогут только 24 студента, поэтому ответ не меньше 2.
Следующий алгоритм перераспределяет студентов по дням, переместив каждого студента не более чем на 2 дня.
- \(6, 14, 70, 1\) — исходная запись студентов;
- \(6, 70, 14, 1\) — перенесли всех студентов с третьего дня на второй, а всех студентов со второго дня на третий;
- \(70, 6, 14, 1\) — перенесли всех студентов со второго дня на первый, а всех студентов с первого дня на второй;
- \(70, 6, 11, 4\) — перенесли трех студентов с третьего дня на четвертый;
- \(70, 3, 14, 4\) — перенесли трех студентов со второго дня на третий;
Заметим, что каждый студент был перемещен не более чем на два дня от своей исходной записи.
4 6 14 70 1 70 3 16 5
2
1 2 2
0
1 3 2
-1