CF182C Optimal Sum

又一道关于数组的问题。给定一个正整数 $len$ 和一个包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ 的数组 $a$。我们为该数组定义两个特性： - 我们考虑数组中从第 $i$ 个位置开始，长度为 $len$ 的任意区间。记 $\left| \sum_{j=0}^{len-1} a_{i+j} \right|$ 为所选区间的“模和”。也就是说，模和是该长度为 $len$ 的区间内各整数之和的绝对值。 - 记 $\max$ 所有不同起点 $i$ （$1 \leq i \leq n - len + 1$）上对应模和的最大值为“最优和”。也就是说，最优和是长度为 $len$ 的所有区间模和的最大值。 你的任务是在最多做 $k$ 次以下操作后，计算该数组的最优和的最大可能值：每次操作可以任意选取一个数组中的数 $a_i$，将其乘以 $-1$，即将 $a_i$ 替换为 $-a_i$。每个数可以被多次选择，每次操作累加计数，但总次数不超过 $k$。 你的任务是，经过不超过 $k$ 次上述操作后，计算该数组可能获得的最大“最优和”。

第一行包含两个整数 $n$ 和 $len$（$1 \leq len \leq n \leq 10^{5}$），分别表示数组元素的个数和要选择的区间长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \leq 10^{9}$），表示原数组。 第三行包含一个整数 $k$（$0 \leq k \leq n$），表示可以操作的最大次数。 所有数字之间以一个空格分隔。

输出不超过 $k$ 次允许操作后可能获得的最大“最优和”。 请不要在 C++ 中使用 %lld 读取或输出 64 位整数。推荐使用 cin、cout 流或者 %I64d 进行输入输出。

由 ChatGPT 5 翻译