#P8743. B

    ID: 8837 传统题 10000ms 1024MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>动态规划贪心CF2100前缀和模拟构造

B

Problem B:数轴上的环

题目描述

数轴上有 nn 个点,编号为 11 到 nn。令 x1=0x_1=0,对于 1≤i<n1\le i<n,有 xi+1=xi+aix_{i+1}=x_i+a_i。因此,aia_i 为负数时,第 i+1i+1 个点位于第 ii 个点的左侧;不同编号的点可以位于同一坐标。

请选择恰好 mm 个不同编号的点,并将它们按某种顺序连接成一个环。例如,可以按 1→3→2→4→11\to3\to2\to4\to1 的顺序连接。

环上相邻两点 u,vu,v 的距离为 ∣xu−xv∣|x_u-x_v|。基础收益为环上全部相邻点对的距离之和,包括最后一个点到第一个点的距离。

对于环上的每个点,如果它的前驱、后继的编号均比它小,或者均比它大,再获得 ana_n 的收益。ana_n 可以为负数,此时这项收益为负。

求最大总收益。只需输出收益,不需要输出连接方案。

当 m=1m=1 时,唯一的点的前驱、后继均为它自己,距离和及额外收益均为 00。当 m=2m=2 时,两点之间的距离计入两次,两个点均获得额外收益。

输入格式

第一行两个整数 n,mn,m。

第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。前 n−1n-1 个数给出坐标差,最后一个数为额外收益。

输出格式

输出一行一个整数,表示最大总收益。答案可能为负数。

样例

4 2
1 1 -1 1
6

数据范围

1≤m≤n≤5001\le m\le n\le500,−100≤ai≤100-100\le a_i\le100。

本题评测时限为 1010 秒,内存限制为 10241024 MiB。

参考附件

原题资料