Задача №115407. Милые подпоследовательности
Пусть \(i\)-я подпоследовательность содержит элементы с индексами \(j_1 < \ldots < j_l\). Ценностью этой подпоследовательности называется максимальное значение \(a_{j_m} + m\) по всем \(m\) от \(1\) до \(l\).
Стоимостью разбиения массива на \(k\) подпоследовательностей называется сумма ценностей этих подпоследовательностей.
Найдите максимальную стоимость разбиения.
Первая строка содержит два целых положительных числа \(n\) и \(k\) (\(1 \leq k \leq n \leq 500\,000\)) — размер массива и количество подпоследовательностей, на которые его надо разбить.
Вторая строка содержит \(n\) целых положительных чисел \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \leq a_i \leq 10^9\)) — элементы массива.
Выведите максимальную стоимость разбиения данного массива на \(k\) непустых подпоследовательностей.
В тестовом примере массив можно разбить на \([3, 10]\), \([7]\), \([1, 2]\). Тогда ответ будет равен \((10 + 2) + (7 + 1) + (2 + 2) = 12 + 8 + 4 = 24\).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(k\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 14 | \(n \le 8\) | – | 0 | |
| 2 | 19 | – | \(k = 2\) | – | |
| 3 | 17 | – | – | – | \(a_{i+1} \leq a_i\) |
| 4 | 21 | – | – | – | \(a_{i + 1} \geq a_i - 1\) |
| 5 | 15 | \(n \leq 1000\) | – | 0, 1 | |
| 6 | 14 | – | – | 0 – 5 | |
5 3 3 7 10 1 2
24