Погрузка багажа
(Время: 2 сек. Память: 32 Мб Сложность: 28%)
В одном аэропорту багаж везут для погрузки на самолёт в N прицепленных друг за другом тележках. Тележки пронумерованы от 1 до N. 1-я тележка присоединена к тягачу.
У каждой тележки есть два параметра: вместимость и прочность крепления.
Вместимость – это количество единиц груза, которое можно поместить на тележку.
Прочность крепления характеризует суммарное количество единиц груза, которое это крепление может выдержать; это сумма масс груза на самой тележке и на всех тележках, находящихся позади текущего крепления. Заметим, что учитывается только масса багажа, а не самих тележек.
Вместимость i-й тележки равна Ci, прочность крепления i-й тележки равна Si .
Инструкция предписывает загружать тележки так, чтобы груз располагался как можно дальше от тягача и как можно ближе к концу автопоезда. Это означает, что сначала необходимо погрузить на тележку номер N весь багаж, который на неё можно поместить, далее приходит очередь тележки номер N-1 и так далее до тележки номер 1, которая, напоминаем, крепится к тягачу.
По заданным параметрам N, Ci и Si определите для каждой тележки максимальную массу багажа, который нужно на неё погрузить с учётом её вместимости и прочности креплений всех тележек от 1-й до i-й.
Входные данные
В первой строке входного файла INPUT.TXT данных содержится число N – общее количество тележек в автопоезде. Тележки нумеруются от 1 до N, первая тележка крепится к тягачу, вторая крепится к первой и так далее до тележки с номером N .
В следующих N строках содержатся значения вместимости тележек Ci по одному в строке. После этого в следующих N строках содержатся значения прочности креплений тележек Si. Параметры, описывающие i-ю от начала автопоезда тележку, находятся в строках с номерами i+1 и N+i+1 .
Все числа во входных данных целые, 1 ≤ N ≤ 105, 1 ≤ Ci, Si ≤ 109.
Выходные данные
В выходной файл OUTPUT.TXT выведите N чисел по одному в строку. Число в i-й строке должно соответствовать максимальному числу единиц груза, который нужно погрузить на эту тележку с учётом её вместимости и прочности креплений всех тележек от 1-й до i-й.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
14
5
6
12
6
25
30
8
19
12 | 12
5
0
2
6
|
Пояснение к примеру
Для пояснения примера из условия запишем данные в следующую таблицу:
| Номер тележки | 1 | 2 | 3 | 4 | 5 |
|---|
| Вместимость | 14 | 5 | 6 | 12 | 6 |
| Прочность крепления | 25 | 30 | 8 | 19 | 12 |
| Ответ | 12 | 5 | 0 | 2 | 6 |
|
Начнём погрузку с последней тележки (номер 5). Её можно загрузить на полную вместимость (6 единиц), так как самое слабое крепление перед ней – у тележки с номером 3 – имеет прочность 8 единиц.
Далее приходит очередь загрузить предпоследнюю тележку номер 4. Её вместимость 12 единиц, но если мы загрузим её полностью, то на крепление тележки номер 3 будет действовать груз в 6+12 = 18 единиц, что больше допустимых 8 единиц. Таким образом, так как 6 единиц уже загружены, на тележку номер 4 можно погрузить только 2 единицы. Так как прочность крепления тележки номер 3 теперь полностью исчерпана, погрузить на неё уже ничего не удастся.
Далее приходим к выводу, что на тележку номер 2 можно погрузить 5 единиц багажа, а на тележку номер 1 – только 12 единиц.
Система оценки
Решения, правильно работающие для случаев, в которых количество тележек не превосходит 100, получат не менее 25 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
