Задача №112764. Оптимальное расписание
Как вы помните, ваш друг работает главным диспетчером в одной из компаний, владеющей сетью маршрутных такси. Недавно директор поставил перед ним задачу оптимизировать расписание маршруток на некотором маршруте.
Экономический отдел предоставил вашему другу прогноз пассажиропотока на следующие \(n\) часов. Теперь необходимо составить расписание маршруток, а именно для каждого часа определить, выйдет маршрутка на линию в этот час или нет. Известно, что если в \(i\)-ый час на маршрут выйдет маршрутка, то она принесет прибыль ai рублей, при этом ai может быть как положительным, так и нулевым или отрицательным. Также, в связи с ограниченным размером автопарка и в соответствии с требованиями департамента транспорта, маршрутки должны работать примерно \(2/3\) всего времени. Более формально, для любого \(i\) (\(1 \le i \le n\)) величина
\(\)b = \frac{t_{work}}{2} - t_{skip}\(\) должна лежать в пределах от \(−k\) до \(k\) включительно. Здесь \(t_{work}\) — количество часов до \(i\)-ого включительно, в которые маршрутки выходили на линию, а \(t_{skip}\) — количество часов до i-ого включительно, в которые маршрутки не выходили на линию. Помогите вашему другу найти максимальную суммарную прибыль маршрута с учетом всех требований.
В первой строке входных данных находится количество часов \(n\), на которые необходимо составить расписание, и число \(k (1 \le n \le 10^5, 1 \le k \le 10\)). На второй строке находятся \(n\) чисел: прогнозируемая прибыль для каждого часа \(a_i\) \((|a_i | \le 10^9\) ). Все числа во входном файле целые.
Выведите одно число — максимальную суммарную прибыль в рублях.
В первом примере оптимально выпустить маршрутки на линию в первый, третий и четвертый часы, таким образом, прибыль составит \(2 + 3 + 4 = 9\) рублей. Величины \(t_{work}, t_{skip}\) и \(b\) после каждого часа представлены в таблице:
Решение, в котором маршрутки выходят на линию в первый, второй, третий и четвертый часы, неправильно, потому что в таком случае уже после третьего часа \(t_{work} = 3, t_{skip} = 0\), а значит, \(b = 1.5\), что недопустимо по условию задачи.
Однако, для второго примера это решение допустимо, так как максимальное значение \(b\) равно 2, что удовлетворяет ограничению. Это решение и является оптимальным.
В третьем примере необходимо выпустить маршрутки на линию во все часы, кроме третьего.
Решения, правильно работающие при \(n \le 20\), оцениваются не менее чем в 20 баллов.
Решения, правильно работающие при \(n \le 1000\), оцениваются не менее чем в 50 баллов.
5 1 2 1 3 4 -5
9
5 2 2 1 3 4 -5
10
5 1 5 5 -10 5 5
20