Кольорове перетворення


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 250M

Author:
Problem type
Allowed languages
C, C++, Java, Python

Задано масив натуральних чисел \(a\), який містить \(n\) елементів. Спочатку всі елементи масиву зафарбовані у синій колір.

Потрібно вибрати \(k\) елементів масиву і пофарбувати їх у жовтий колір. Потім, якщо є хоча б один елемент синього кольору, то робимо наступне:

вибираємо будь-який елемент синього кольору, який має хоча б одного сусіда жовтого кольору, і фарбуємо його в жовтий колір.

Вартість фарбування масиву визначається як сума перших \(k\) обраних елементів і останнього пофарбованого елемента.

Необхідно визначити максимально можливу вартість фарбування.

Входові дані:

Перший рядок стандартного входового потоку містить два натуральних числа \(n\) та \(k\) \((2 \le n \le 10^5; 1 \le k < n)\).

Другий рядок містить \(n\) натуральних чисел \(a1,a2,…,an\) \(( 1 \le ai \le 10^9)\) – де, \(ai\) – вартість форбування і-го елемента.

Виходові дані:

У стандартний виходовий потік виведіть одне натуральне число, що є максимально можливою вартістю фарбування даного масиву.

Приклад входових даних:
5 2
3 4 2 1 2
Приклад виходових даних:
9

Comments

There are no comments at the moment.