#YDOIp2023B. 论翻越坚果的艺术

论翻越坚果的艺术

题目背景

成功,并不是高瞻远瞩。而是你本就站在高处,运筹帷幄,掌控未来。这才是 8848!这才是胸怀天下!顶峰的目标,钛金的气概,真皮的情怀,让我们向成功的人生致敬!

题目描述

现在戴夫又双叒叕在房内举行 ”大喷菇派对“!小 C 怎会放弃这个参与大喷菇派对的机会。但是戴夫还是一如既往的害羞,为了防止小 C 参加大喷菇派对,戴夫在一个长度为 mm 的草坪上种下了 nn 株坚果,第 ii 株坚果的血量为 hih_i。戴夫的房子位于坐标 x=0x=0 处,而小 C 位于坐标 x=mx=m 处。小 C 会沿着坐标轴反方向,向戴夫家移动。但是会被坚果挡住,如果被第 ii 株坚果挡住,需要花 hih_i 的时间吃掉这株坚果才可以继续前进。但是:

一些人渴望走的更远、得到更多,这也促使小 C 从普通成为非凡。那就是撑杆跳小 C !撑杆跳小 C 平时喜欢运动,每日积极训练,现在可以直接翻越坚果。他之前一次训练被小 K 看到了,小 K 当场被震惊。”那简直就是各种高难度动作的缝合怪“ 小 K 这样描述。

小 C 在学校 N 练习了时长两年半的撑杆跳后,终于学会了如何翻越坚果!现在他有一根撑杆,如果当前坐标在 xx 使用这根撑杆后,坐标将会变为 xkx - k,即不会被坐标处于 [xk+1,x][x - k + 1, x] 的坚果挡住。(注意,如果 xk+1x - k+1 小于等于 00,小 C 会直接进入疯狂戴夫的家)撑杆只能使用一次,但是由于学会了翻越坚果的艺术,他不像普通的撑杆跳选手,在第一个坚果处就选择使用撑杆,而是可以在任意时刻选择使用撑杆!

小 C 希望花费最少的时间在吃掉坚果上,小 C 当然是绝对聪明的,他也必然知道什么时候使用撑杆最优。所以这次你是疯狂戴夫!你需要种植这 nn 株坚果,不妨假设第 ii 株坚果种下的坐标为 xix_i,需要满足 1x1<x2<<xnm1 \le x_1 < x_2 < \dots < x_n \le mxix_i 均为正整数。你现在想知道,如果你按最优的方式种植坚果,小 C 也按最优的方式翻越坚果,你最多可以让小 C 花费多久在吃坚果上?以让你的 ”大喷菇派对“ 举办的尽可能久。

形式化题意:

  • 对于一个长度为 mm 的非负整数序列,定义其权值为:选择一个长度为 kk 的区间,将区间内的数变成 00 后,所有数总和的最小值。
  • 给定 nnnn 个正整数 h1,h2,,hnh_1,h_2,\cdots,h_n,你需要选择一个长度为 nn 的正整数序列 xx 满足 1x1<x2<<xnm1 \le x_1 < x_2 < \dots < x_n \le m。然后根据 xx 构造序列 bb:对于任意 i(1in)i(1 \le i \le n)bxi=hib_{x_i}=h_i;对于其余位置 bi=0b_i=0
  • bb 的权值的最大值。

输入格式

第一行输入三个正整数 n,m,kn, m, k

第二行 nn 个正整数 h1,h2,,hnh_1, h_2, \dots, h_n

输出格式

一行一个正整数,表示答案

样例

样例输入 #1

6 9 4
1 1 4 5 1 4

样例输出 #1

6

样例解释 #1

方案可能不唯一,一种最优的方案是:x={1,2,3,7,8,9}x=\{1,2,3,7,8,9\},此时 b={1,1,4,0,0,0,5,1,4}b=\{1,1,4,0,0,0,5,1,4\},选择长度为 44 的区间 [6,9][6,9]bb 的权值为 1+1+4+0+0+0+0+0+0=61+1+4+0+0+0+0+0+0=6

样例输入 #2~#7

见下发文件中的 nut2/3/4/5/6/7.in

样例输出 #2~#7

见下发文件中的 nut2/3/4/5/6/7.ans

样例下载点击这里

数据规模与约定

对于所有数据,有:

  • 1km1091 \leq k \leq m \leq 10^9
  • 1nmin(2×105,m)1 \leq n \leq \min(2 \times 10^5, m)
  • 1hi1091 \leq h_i \leq 10^9

子任务 1(3pts)1(3pts)n=mn=m

子任务 2(10pts)2(10pts)n18n \le 18

子任务 3(11pts)3(11pts)n,m40,hi5n,m \le 40,h_i \le 5

子任务 4(12pts)4(12pts)n,m200,hi5n,m \le 200,h_i \le 5

子任务 5(13pts)5(13pts)n,m2000,hi5n,m \le 2000,h_i \le 5

子任务 6(22pts)6(22pts)hi=1h_i=1

子任务 7(29pts)7(29pts):无特殊限制