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 | 無額外限制。 |