← 返回题目列表

Codeforces · 182/C

C. 最佳总和

中文机器翻译题面 查看原题

这里还有一个关于数组的问题。给定正整数 len 和数组 a,其中包含 n 个整数 a1, a2, ..., an。让我们介绍给定数组的两个特征。

- 让我们考虑长度为 len 的数组的任意区间,从位置 i 开始。值 $$\text{modSum}(i, \text{len}) = \left| \sum_{j=i}^{i+\text{len}-1} a_j \right|$$ 是所选区间上的模和。换句话说,模和是所选区间上长度为 len 的整数之和,取其绝对值。
- 值 $$\max_{1 \leq i \leq n - len + 1} modSum(i, len)$$ 是数组的最佳总和。换句话说,数组的最优和是长度为 len 的数组的各个区间上的所有模和的最大值。

你的任务是计算给定数组 a 的最佳和。然而,在进行计算之前,您只能使用该数组产生不超过 k 个以下形式的连续运算:一次运算意味着从数组 ai 中取出任意数字并将其乘以 -1。换句话说,最多允许您从数组中取出任意数字 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 说明符。

示例

输入 #1

5 3
0 -2 3 -5 1
2

输出 #1

10

输入 #2

5 2
1 -3 -10 4 1
3

输出 #2

14

输入 #3

3 3
-2 -5 4
1

输出 #3

11