P15347 [TOIP 2025] 叠加最大值

在一个正整数数组或子数组中，每个出现的数字乘上它的出现次数，称为它的叠加值。「子数组」是指一个数组中，由连续元素所组成的一部分。例如数组 $[4, 5, 2, 3, 4, 2, 2]$ 中，$5$ 的叠加值是 $5\times1=5$，$4$ 的叠加值是 $4\times2=8$，$3$ 的叠加值是 $3\times1=3$，而 $2$ 的叠加值是 $2\times3=6$。 输入一个长度为 $n$ 的正整数数组以及一个正整数 $k$，本题要求每一个长度为 $k$ 的子数组中的最大叠加值。一共有 $n-k+1$ 个长度为 $k$ 的子数组，输出这 $n-k+1$ 个最大叠加值的总和。 举例来说，输入数组是 $[4, 5, 2, 3, 4, 2, 2, 5]$，$n=8$，$k=5$，各个子数组的最大叠加值如下： * $[4, 5, 2, 3, 4]$ 的最大叠加值是 $4\times2=8$。 * $[5, 2, 3, 4, 2]$ 的最大叠加值是 $5\times1=5$。 * $[2, 3, 4, 2, 2]$ 的最大叠加值是 $2\times3=6$。 * $[3, 4, 2, 2, 5]$ 的最大叠加值是 $5\times1=5$。 所有最大叠加值的总和是 $8+5+6+5=24$。

$$ \begin{aligned} &n \; k \\ &c_0 \; c_1 \; \cdots \; c_{n-1} \end{aligned} $$ - $n$ 为数组的长度。 - $k$ 为所要求子数组的长度。 - $c_i$ 为数组中的第 $i$ 个正整数。

$X$ - $X$ 为所有叠加最大值的总和。

### 数据限制 * $1 \le n\le 10^5$。 * $1 \le k \le n$。 * $1 \le c_i < 2^{31}$。 ### 评分说明 本题共有三组子任务，条件限制如下所示。 每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 6 | 输入满足$N \le 1000$， 且$c_i \le 10^6$。 | | 2 | 38 | 输入满足数组数字均不相等。 | | 3 | 56 | 无额外限制。 |