11212. Коштовності

Бали: 100

Time limit: 1.0s

Memory limit: 250M

Author:

Problem type

Allowed languages

C++, Java, Pascal, Python

Твій друг подарував тобі \(D\) на день народження. \(D\) - це горизонтальний циліндр, який містить ряд із \(N\) коштовностей.

Значення коштовностей: \(V_1, V_2, ..., V_N\) зліва направо.

Можуть бути коштовності з від’ємними значеннями. Спочатку у вас немає коштовності в руках.

Ви можете виконати щонайбільше \(K\) операцій на \(D\) (можливо, нуль):

Операція \(A\): Вийміть крайній лівий коштовний камінь, що міститься в \(D\), і тримайте його в руці. Ви не можете виконати цю операцію, коли \(D\) порожній.
Операція \(B\): Вийміть самий правий коштовний камінь, що міститься в \(D\), і тримайте його в руці. Ви не можете виконати цю операцію, коли \(D\) порожній.
Операція \(C\): Виберіть коштовний камінь у ваших руках і вставте його в лівий кінець \(D\). Ви не можете зробити цю операцію, якщо у вас немає коштовності в руках.
Операція \(D\): виберіть коштовний камінь у ваших руках і вставте його в правий кінець \(D\). Ви не можете зробити цю операцію, якщо у вас немає коштовності в руках.

Знайдіть максимально можливу суму коштовностей у ваших руках після операцій.

Перший рядок вхідного потоку містить цілі числа \(N,K\) (\(1 \le N \le 50\), \(1 \le K \le 100\)).

Другий рядок містить цілі числа \(V_1, V_2, ..., V_N\) (\(-10^7 \le V_i \le 10^7\)).

У вихідний потік вивести шукану суму.

До прикладу 1:

Після наступної послідовності операцій у вас в руках є два коштовності 8 і 6, що становить 14 і це є максимальним результатом.

Виконайте операцію \(A\). Ви виймаєте коштовність значення -10 з лівого кінця \(D\).
Виконайте операцію \(B\). Ви дістаєте коштовний камінь вартістю 6 з правого кінця \(D\).
Виконайте операцію \(A\). Ви дістаєте коштовний камінь вартістю 8 з лівого кінця \(D\).
Виконайте операцію \(D\). Ви вставляєте коштовний камінь значення -10 у правий кінець \(D\).

6 4
-10 8 2 1 2 6

6 4
-6 -100 50 -2 -5 -3

6 3
-6 -100 50 -2 -5 -3

Коментарі

Ще немає коментарів.