Ограничения: время – 150ms/250ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Мистер Ким строит защитную стену около города, стараясь огородить все дома. По проекту стена имеет форму непрерывной ломаной линии из отрезков,
параллельных осям координат. Ось X проходит вдоль главной улицы. На `j`-м участке главной улицы стена может находиться
от неё на расстоянии `D_j` единиц, чтобы защитить `D_j` домов на поперечной улице.
На каждый единичный отрезок стены необходим один защитник (на рисунке красным показана линия стены, а
красными точками - места размещения защитников), но защитников всего `K`.
Поэтому нужно изменить форму стены таким образом, чтобы её длина не превышала `K`, а количество домов за стеной было как можно больше. Начало и конец стены должны располагаться на главной улице. Если стена защищает ненулевое количество домов на первой или последней из поперечных улиц, боковой отрезок стены вдоль них к главной улице тоже нужно защищать.
При этом стена не должна огораживать пустые участки земли. Поскольку точное число защитников пока неизвестно,
нужно найти ответ для нескольких разных значений `K`.
В первой строке ввода содержатся два целых числа: длина главной улицы `N` (`1 <= N <= 10^5`) и количество
запросов `T` (`1 <= T*N <= 10^5`) с различным количеством защитников.
Во второй строке содержатся `N` целых чисел `D_j` (`0 <= D_j <= 10^9`) - количество домов на `j`-й поперечной к главной улице.
В третьей строке содержатся `T` различных целых чисел `K_i` (`N <= K_i <= 10^{18}`) в порядке убывания - количество защитников в каждом из запросов.
Выведите `T` строк, по одной для каждого из запросов.
Каждая строка должна состоять из `N` целых чисел `C_j` (`C_j <= D_j`, количество огороженных
домов на `j`-й поперечной улице) через пробел - исправленный план строительства стены, в котором длина
стены не будет превышать `K_i`. Если существует несколько вариантов с максимальным суммарным количеством домов за стеной, то
можно вывести любой вариант.
```sample Пример ввода:
5 4
0 2 0 1 1
15 9 8 6
```
```sample Вывод для примера:
0 2 0 1 1
0 1 0 1 1
0 0 0 1 1
0 0 0 0 0
```
Пояснение к `K=8`: за стеной окажутся 2 дома из 4, длина получившейся стены будет равна 7, и для ее охраны хватит 8 защитников.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (40 баллов)||
`1<=N<=100`, `T*N<=100`, `N<=K_i<=10000`, `0<=D_j<=100`
||.u|Подзадача 2 (30 баллов)||
`100<N<=1000`, `T*N<=1000`, `N<=K_i<=10^5`, `0<=D_j<=100`
Необходимые подзадачи: 1
||.u|Подзадача 3 (20 баллов)||
`1000<N<=10^5`, `T*N<=10^5`, `N<=K_i<=10^{10}`, `0<=D_j<=10^5`
Необходимые подзадачи: 1, 2
||.u|Подзадача 4 (10 баллов)||
`1000<N<=10^5`, `T*N<=10^5`, `N<=K_i<=10^{18}`, `0<=D_j<=10^9`
Необходимые подзадачи: 1, 2, 3
Баллы за каждую из подзадач начисляются только в случае,
если все тесты для этой подзадачи успешно пройдены. По запросу сообщается результат о первой ошибке.
Начало
Рабочее место участника
Стеки, очереди