TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5407
  • 题目
  • P5407【欢乐的痛苦赛】赚钱的游戏
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    问题描述

    一个nc此时高调路过,他看到了nodgd名字中的字母n,高兴地拍了拍nodgd的肩膀说:“好巧啊,你也是nc!”

    nodgd觉得眼前的nc很烦,就掏出 \(n\) 堆石子排成一列,对nc说:“我们来玩个游戏。游戏开始前,你有一次机会选择一堆石子,往里面添加 \(k\) 个石子或者拿走 \(k\) 个石子,也可以不进行这个操作;此后你每次可以选择两堆相邻的石子合并在一起,然后放回原来的位置,直到最后只剩一堆石子;如果这两堆石子的个数分别是 \(x\)\(y\) ,则这一次合并的时候我给你 \(xy\) 元人民币。但是,你要先给我 \(m\) 元人民币我才和你玩这个游戏。怎么样,来不来玩玩?”

    nc觉得这是一个发家致富的好机会,果断的答应了下来。

    作为一个低调路过的路人甲,你并不打算参与游戏,只是默默的在心中算了算nc如果玩这个游戏最多可以赚多少钱。

    输入格式

    输入数据共两行。

    第一行有三个整数 \(n,m,k\) ,分别表示石子的堆数,开局前nc需要支付的人民币数额,开始合并前可以添加或者拿走的石子数量。

    第二行 \(n​\) 个整数,表示每堆石子的数量 \(a_1,a_2,\dots,a_n​\) 。注意,nodgd的石子有些违背常理, \(a_i​\) 可能是负数。

    输出格式

    输出数据共一行。

    第一行有一个整数,表示nc玩这个游戏最多可以赚多少钱。

    样例输入

    3 6 1
    1 1 1

    样例输出

    -1

    提示

    输入输出样例1说明

    三堆石子的数量分别是 $1,1,1$ 。一开始,可以任选一堆石子增加 $1$ 个,例如变成 $2,1,1$ ;或者拿走 $1$ 个,例如变成 $1,0,1$ ;或者什么都不做,仍然是 $1,1,1$ 。此后,进行合并操作,在 $2,1,1 $ 的局面下最多拿到 $5$ 元人民币,但开局前支付了 $6$ 元人民币,会亏损 $1$ 元人民币。可以验证没有不亏损的方法,所以最多赚取 \(-1\) 元人民币。

    数据规模与约定

    前 $10\%$ 的数据, $n\leq 10 $ ;

    前 $60\%$ 的数据, \(n\leq 100\)

    全部的测试数据, $1\leq n\leq 105,\ |m|\leq10{18},\ 1\leq k\leq 104,\ |a_i| \leq 104 $ 。


    来源  感谢nodgd命题