#YDOIp2023B. 论翻越坚果的艺术
论翻越坚果的艺术
题目背景
成功,并不是高瞻远瞩。而是你本就站在高处,运筹帷幄,掌控未来。这才是 8848!这才是胸怀天下!顶峰的目标,钛金的气概,真皮的情怀,让我们向成功的人生致敬!
题目描述
现在戴夫又双叒叕在房内举行 ”大喷菇派对“!小 C 怎会放弃这个参与大喷菇派对的机会。但是戴夫还是一如既往的害羞,为了防止小 C 参加大喷菇派对,戴夫在一个长度为 的草坪上种下了 株坚果,第 株坚果的血量为 。戴夫的房子位于坐标 处,而小 C 位于坐标 处。小 C 会沿着坐标轴反方向,向戴夫家移动。但是会被坚果挡住,如果被第 株坚果挡住,需要花 的时间吃掉这株坚果才可以继续前进。但是:
一些人渴望走的更远、得到更多,这也促使小 C 从普通成为非凡。那就是撑杆跳小 C !撑杆跳小 C 平时喜欢运动,每日积极训练,现在可以直接翻越坚果。他之前一次训练被小 K 看到了,小 K 当场被震惊。”那简直就是各种高难度动作的缝合怪“ 小 K 这样描述。
小 C 在学校 N 练习了时长两年半的撑杆跳后,终于学会了如何翻越坚果!现在他有一根撑杆,如果当前坐标在 使用这根撑杆后,坐标将会变为 ,即不会被坐标处于 的坚果挡住。(注意,如果 小于等于 ,小 C 会直接进入疯狂戴夫的家)撑杆只能使用一次,但是由于学会了翻越坚果的艺术,他不像普通的撑杆跳选手,在第一个坚果处就选择使用撑杆,而是可以在任意时刻选择使用撑杆!
小 C 希望花费最少的时间在吃掉坚果上,小 C 当然是绝对聪明的,他也必然知道什么时候使用撑杆最优。所以这次你是疯狂戴夫!你需要种植这 株坚果,不妨假设第 株坚果种下的坐标为 ,需要满足 且 均为正整数。你现在想知道,如果你按最优的方式种植坚果,小 C 也按最优的方式翻越坚果,你最多可以让小 C 花费多久在吃坚果上?以让你的 ”大喷菇派对“ 举办的尽可能久。
形式化题意:
- 对于一个长度为 的非负整数序列,定义其权值为:选择一个长度为 的区间,将区间内的数变成 后,所有数总和的最小值。
- 给定 和 个正整数 ,你需要选择一个长度为 的正整数序列 满足 。然后根据 构造序列 :对于任意 ,;对于其余位置 。
- 求 的权值的最大值。
输入格式
第一行输入三个正整数 。
第二行 个正整数 。
输出格式
一行一个正整数,表示答案
样例
样例输入 #1
6 9 4
1 1 4 5 1 4
样例输出 #1
6
样例解释 #1
方案可能不唯一,一种最优的方案是:,此时 ,选择长度为 的区间 , 的权值为 。
样例输入 #2~#7
见下发文件中的 nut2/3/4/5/6/7.in
样例输出 #2~#7
见下发文件中的 nut2/3/4/5/6/7.ans
数据规模与约定
对于所有数据,有:
子任务 :
子任务 :
子任务 :
子任务 :
子任务 :
子任务 :
子任务 :无特殊限制
Related
In following contests: