Codeforces Round 117 (Div. 2) |
---|
Закончено |
Перед Вами вновь задача на массивы. Вам задан массив a состоящий из n целых чисел a1, a2, ..., an, а также целое положительное число len. Введем две характеристики для заданного массива.
В задаче от Вас требуется посчитать оптимальную сумму заданного массива a. Однако, прежде чем производить вычисления, Вам разрешено произвести не более k последовательных операций с этим массивом следующего вида: за одну операцию разрешается взять произвольное число массива ai и умножить его на -1. Другими словами, не более k раз разрешается взять произвольное число массива ai и заменить его на - ai. Каждое число массива разрешается выбирать произвольное количество раз.
Требуется посчитать максимально возможную оптимальную сумму массива после выполнения не более k операций, указанных выше.
В первой строке заданы два целых числа n, len (1 ≤ len ≤ n ≤ 105) — количество элементов в массиве и длина выбираемого подотрезка массива, соответственно.
Во второй строке задана последовательность из n целых чисел a1, a2, ..., an (|ai| ≤ 109) — исходный массив.
В третьей строке задано единственное целое число k (0 ≤ k ≤ n) — допустимое количество операций.
Все числа в строках разделены ровно одним пробелом.
В единственной строке выведите максимально возможную оптимальную сумму после выполнения не более k допустимых операций.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++, вместо него рекомендуется использовать потоки cin, cout, а также спецификатор %I64d.
5 3
0 -2 3 -5 1
2
10
5 2
1 -3 -10 4 1
3
14
3 3
-2 -5 4
1
11
Название |
---|