Codeforces Round 538 (Div. 2) |
---|
Закончено |
Массив $$$b$$$ называется подмассивом массива $$$a$$$, если он образует непрерывный подотрезок $$$a$$$, то есть равен $$$a_l$$$, $$$a_{l + 1}$$$, $$$\ldots$$$, $$$a_r$$$ для некоторых $$$l, r$$$.
Пусть $$$m$$$ — некоторая зафиксированная константа. Для любого массива, содержащего хотя бы $$$m$$$ элементов, определим его симпатичность, как сумму $$$m$$$ наибольших элементов этого массива. Например:
Вам дан массив $$$a_1, a_2, \ldots, a_n$$$, значение константы $$$m$$$ и целое число $$$k$$$. Вам нужно разбить массив $$$a$$$ на ровно $$$k$$$ подмассивов таких, что:
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m$$$, $$$2 \le k$$$, $$$m \cdot k \le n$$$) — количество элементов в $$$a$$$, константа $$$m$$$ в условии и количество подмассивов, на которые нужно разбить.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
В первой строке выведите наибольшую возможную сумму симпатичностей подмассивов в разбиении.
Во второй строке выведите $$$k-1$$$ целых чисел $$$p_1, p_2, \ldots, p_{k-1}$$$ ($$$1 \le p_1 < p_2 < \ldots < p_{k-1} < n$$$) определяющих разбиение массива.
В случае если есть несколько оптимальных разбиений, выведите любое из них.
9 2 3 5 2 5 2 4 1 1 3 2
21 3 5
6 1 4 4 1 3 2 2 3
12 1 3 5
2 1 2 -1000000000 1000000000
0 1
В первом примере одно из оптимальных разбиений выглядит как $$$[5, 2, 5]$$$, $$$[2, 4]$$$, $$$[1, 1, 3, 2]$$$.
Таким образом, суммарная симпатичность равна $$$10 + 6 + 5 = 21$$$.
Во втором примере одно из оптимальных разбиений выглядит как $$$[4]$$$, $$$[1, 3]$$$, $$$[2, 2]$$$, $$$[3]$$$.
Название |
---|