P11743 Dynamic Array Problem

你有一个序列长度为 $n$ 的序列 $a$！初始时序列只有两端有隔板，其他位置没有。 你可以插入任意多个隔板，隔板不重合，且隔板不起到分割序列的作用。插入后，选择至多 $k$ 对 **可以不相邻** 的隔板，将他们之间的序列元素翻转。它们之间的隔板的位置不受影响，只改变元素位置，要求一个元素至多被翻转一次。 如果两个隔板相邻且他们之间的元素下标是 $l$ 到 $r$，则会对总贡献产生的权值为：$\sum\limits_{i=l}^{r} a_i \times (i - l + 1)$。求操作后的总贡献的最大值。

无

无

**【样例解释 $\mathbf 1$】** 序列初始两端各有一个隔板。在序列第 $2$ 个位置，第 $7$ 个位置，第 $8$ 个位置后添加隔板。并将第 $1$ 个位置到第 $7$ 位置中间的元素翻转。最后得到的序列权值为 $10$。可以证明不存在比这更大的权值。 **【样例解释 $\mathbf 2$】** 本题提供大样例，该数据满足 `Subtask 3` 的限制。具体求解不做解释。 --- **【数据规模与约定】** **本题开启子任务捆绑测试**。本题自动开启 O2 优化。 * Subtask 1（15 pts）：$n\leq 20$。 * Subtask 2（45 pts）：$n\leq 100$。 * Subtask 3（40 pts）：$n\leq 550$。 对于所有测试点满足 $1\leq n \leq 550$，$1\leq k \leq n$，$-10^9 \leq a_i \leq 10^9$。