AT_waipc_qual_g Sum of Max of Sum of K Segments

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和一个整数 $K$。定义函数 $f(L,R)$（$1 \leq L \leq R \leq N$）如下： - 当 $R-L + 1 < K$ 时，令 $f(L,R)=0$。 - 否则，考虑从 $(A_L,A_{L+1},\ldots,A_R)$ 中取出 $K$ 个不相交的非空连续子序列。将“最左侧子序列的元素和的绝对值”与“其他子序列的元素和”相加，取所有可能方案中该值的最大值，作为 $f(L,R)$。更形式化地，$f(L,R)=\max_{L\leq l_1\leq r_1

输入通过标准输入给出，格式如下： > $N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

请输出答案。

### 样例解释 1 对于满足 $K \leq R-L+1$ 的 $(L,R)$，$f(L,R)$ 的值如下： - 当 $(L,R)=(1,2)$ 时，$(l_1,r_1,l_2,r_2)=(1,1,2,2)$ 能取得最大值，因此 $f(L,R)=0$。 - 当 $(L,R)=(1,3)$ 时，$(l_1,r_1,l_2,r_2)=(1,1,3,3)$ 能取得最大值，因此 $f(L,R)=1$。 - 当 $(L,R)=(2,3)$ 时，$(l_1,r_1,l_2,r_2)=(2,2,3,3)$ 能取得最大值，因此 $f(L,R)=1$。 因此，这些 $f(L,R)$ 的总和为 $2$，即答案为 $2$。 ### 数据范围 - $1 \leq K \leq N \leq 250000$ - $K \leq 4$ - $-10^9 \leq A_i \leq 10^9$ - 输入均为整数。 由 ChatGPT 5 翻译