配点 : 1100 点
問題文
有一天,真田去了卡上。
您需要抽 N 牌。
真田按照指示做了,抽了一张牌。
这张卡的正面和背面都写有数字,2 写在侧面的数字之和始终为
这是 M 。真田拉
在 N 卡片中,i 桌子上写的数字是 A_i 。
接下来,kaage 执行以下操作。 K 次内的任意次数 (0 次)。
满足
- 1 \leq x\leq y\leq N 的任意整数 对于 x,y ,x 页面 y 将所有卡片翻至第一张。
真田起了疑心,派了一名间谍到卡上家。N 我了解到,卡片正面所写数字的总和越多,kaage 就必须学习得越多。
为了让 kaage 学习的 sanada,通过适当的次数和适当的操作 N 求出可以将卡片正面所写数字的总和最大化到多少。
制約
- 所有输入均为整数。
- 1 \leq N \leq 10^6
- 0 \leq K \leq N
- 1 \leq M \leq 10^9
- 1 \leq A_i \leq M-1
小課題
这项作业需要 3 有两个子作业。- (400 点) N \leq 2000
- (400 点) N \leq 10^5
- (300 分)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N M K
A_1 A_2 \ldots A_N
出力
当进行适当的次数和适当的操作时,所有卡片正面所写数字的总和最大值 1 行输出。
注意
小課題 1 在提交仅针对 求得最大值 的代码时N 是 在 2000,该进程将立即终止。
入力例1
3 6 1
3 3 4
出力例1
10
在这种情况下,例如如果一次操作都不进行时,卡片正面所有数字的总和最大 10 。
入力例2
8 9 2
1 3 8 7 5 3 5 1
出力例2
52
例如,通过像下面这样选择区间并进行操作,可以得到最大值 52 可以实现。
- 1 回目: 1 页面 5 反转第 枚卡片的正反面。操作后的卡片排列为 {8, 6, 1, 2, 4, 3, 5, 1}。
- 2 回目: 3 页面 8 反转第 枚卡片的正反面。操作后的卡片排列为 {8, 6, 8, 7, 5, 6, 4, 8}。
作者: sanadayukimura73