Задача D. Постепенность
Задачу добавил: alef
Успешно сдано решений: 104
Мэр города S полагает, что радикальное сокращение количества остановок популярного трамвайного маршрута вызовет серьёзное недовольство горожан. Поэтому он решил уменьшать количество остановок постепенно.
В настоящий момент маршрут состоит из n остановок, последовательно занумерованных числами от 1 до n. Мэр полагает, что на первом этапе не стоит убирать более двух остановок подряд. По техническим причинам убрать первую и последнюю остановки пока нельзя.
По мнению мэра, любому пассажиру, чтобы сесть в трамвай, придётся пройти не более одной остановки пешком (либо «назад», либо «вперёд»).
Для каждой остановки известно количество пассажиров, садящихся в трамвай. На последней остановке в трамвай никто не садится.
Мэр хочет, чтобы суммарное расстояние, измеренное в количестве остановок, пройденных пассажирами перед посадкой, было максимально возможным. Ваша задача — вычислить, каким будет это суммарное расстояние, а также определить, какие остановки должны остаться в маршруте.
В первой строке содержится целое число n (5 ≤ n ≤ 3·105) — исходное количество остановок в маршруте.
Во второй строке содержится n - 1 целое число p1, p2, ..., pn - 1 (1 ≤ pj ≤ 106, j = 1, 2, ..., n - 1), где pj — количество пассажиров, садящихся в трамвай на остановке #j.
В первой строке выведите два целых числа m и q — максимально возможное суммарное расстояние, измеренное в количестве остановок, пройденных пассажирами перед посадкой, и количество остановок, которые останутся в маршруте.
Во второй строке выведите q целых чисел — номера остановок, которые останутся в маршруте. Выводите номера в порядке увеличения.
Подзадача 1 (до 20 баллов)
5 ≤ n ≤ 100, 1 ≤ pi ≤ 100, i = 1, 2, ..., n
Баллы начисляются в случае прохождения всех тестов группы.
Подзадача 2 (до 80 баллов)
Все величины из условия могут принимать любые допустимые значения.
Баллы начисляются в случае прохождения всех тестов группы.
По запросу сообщается номер первого непройденного теста в группе.
10
5 3 8 2 4 9 2 5 1
30 4
1 4 7 10
10
2 7 5 6 4 3 3 2 1
22 5
1 3 6 9 10
Поясним приведённые примеры.
В первом примере в маршруте будет оставлено 4 остановки: #1, #4, #7 и #10. Пассажиры, которые привыкли садиться на других остановках, будут вынуждены пойти на одну из оставшихся.
По мнению мэра, пассажиры, которые обычно садятся на остановке #2, отправятся на остановку #1. Всего таких пассажиров 3, поэтому суммарно они пройдут расстояние в 3 остановки.
Пассажиры, которые обычно садятся на остановке #3, пойдут на остановку #4. Таких пассажиров 8, они пройдут расстояние в 8 остановок, и суммарное расстояние станет равным 11.
На остановку #4 придут и 4 пассажира с ликвидированной остановки #5, увеличив суммарное расстояние ещё на 4 остановки (оно станет равным 15).
Каждый из 9 пассажиров с остановки #6 пройдёт расстояние в одну остановку до остановки #7, и теперь суммарное расстояние составит 24 остановки. Также на остановку #7 придут 5 пассажиров с остановки #8, что прибавит к ответу 5 (итого 29).
Наконец, единственному пассажиру с остановки #9 потребуется идти до остановки #10, что увеличит ответ ещё на единицу.
Таким образом, суммарное расстояние, измеренное в пройденных остановках (быть может, уместно называть это человеко-остановками), окажется равным 30.
Во втором примере существует несколько правильных ответов.
Как легко видеть, из маршрута будут удалены остановки #2, #4, #5, #7 и #8. Это значит, что каждый из пассажиров, привыкших садиться на этих остановках, будет вынужден проделать путь длиной в одну остановку. Поэтому пройденное ими суммарное расстояние будет равно общему количеству пассажиров на этих остановках, т.е. 7 + 6 + 4 + 3 + 2 = 22.
Маршрут, в котором останется 4 остановки, а именно #1, #4, #7 и #10, также будет приводить к суммарному расстоянию в 22 остановки.