Задача №115382. Дорожный патруль
После открытия новой платной трассы М123 возникла проблема установки ограничения скорости. Так как на новую трассу ушло немало средств, было решено возместить часть затрат за счёт штрафов водителей, которые превышают ограничение скорости.
Мы можем выбрать целое неотрицательное число \(k\) для ограничения скорости, после которого происходит следующий процесс. Известно, что по трассе мимо патруля будут ехать \(n\) машин, причём патруль будет наблюдать их в порядке \(1, 2, \ldots, n\). Скорость \(i\)-й машины в тот момент, в который её увидит патруль, будет равна \(a_i\). Если \(a_i > k\), то машина будет остановлена, и водитель заплатит штраф \(a_i - k\). Но водители следующих \(t\) машин (т.е. с номерами \(i + 1, i + 2, \ldots, i + t\)) увидят, что машину остановил патруль, и они сбавят скорость так, что их уже не за что будет останавливать. Далее процесс будет повторяться аналогично.
Вам требуется выбрать такое \(k\), чтобы максимизировать сумму денег, которую можно собрать через штрафы.
Первая строка содержит два целых числа \(n\) и \(t\) (\(1 \leq t \leq n \leq 200\,000)\) — общее количество машин и количество машин, которые снижают скорость непосредственно после каждой остановленной машины.
Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)) — скорости машин.
Выведите одно целое число — максимальную суммарную величину штрафов, которую можно собрать при оптимальном ограничении скорости \(k\).
Тесты к этой задаче состоят из примеров и \(5\) групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(t\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 18 | \(n \leq 3000\) | – | 0 | – |
| 2 | 21 | – | – | – | \(a_i = i\) |
| 3 | 23 | – | \(t \geq 3000\) | – | – |
| 4 | 19 | – | \(t = 1\) | – | – |
| 5 | 19 | – | – | 0 – 4 | – |
В первом примере \(k=0\) (движение перекрыто), штраф заплатят первая и третья машины.
Во втором примере ответ 1 получается при любом из значений \(k\) от \(0\) до \(2\).
В третьем примере выгодно выбрать \(k=2\), тогда получится остановить третью и шестую машину, которые едут со скоростями \(6\) и \(9\), что позволит получить штрафы в сумме \((6 - 2) + (9 - 2) = 11\). Обратите внимание, что первые две машины мы не остановим, потому что их скорости не превышают ограничения.
В четвёртом примере оптимально сделать ограничение по скорости равным \(1\). В таком случае мы остановим первую, пятую и десятую машины и получим суммарный штраф \((5 - 1) + (8 - 1) + (11 - 1) = 21\) .
3 1 1 2 3
4
3 2 1 2 3
1
7 2 1 2 6 3 1 9 2
11
10 3 5 3 7 1 8 10 2 8 1 11
21