← 返回题目列表

AtCoder · tkppc4_1_p

P. 翻页卡

中文机器翻译题面 查看原题

配点 : 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 有两个子作业。
  1. (400 点) N \leq 2000
  2. (400 点) N \leq 10^5
  3. (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