分数: 700 点
问题陈述
Snuke 决定使用机器人来打扫他的房间。
有 N 数轴上的垃圾碎片。 的 i从左边算起的第块位于位置 x_i。 我们想将它们全部放入以下位置的垃圾桶中: 0.
对于垃圾的位置, 0 < x_1 < x_2 < ... < x_{N} \leq 10^{9} 成立。
机器人初始位置 0。 它可以沿着数轴自由左右移动,到达该位置时捡起一块垃圾,携带任意数量的垃圾到达位置后放入垃圾桶 0。除垃圾桶外,严禁将垃圾扔到任何地方。
机器人消耗 X 机器人捡起一块垃圾或将一块垃圾放入垃圾桶时获得能量点。 (将任意数量的垃圾放入垃圾桶会消耗 X 能量点。) 此外,机器人还消耗 (k+1)^{2} 移动距离的能量点 1 当机器人携带 k 垃圾。
找出将所有的能量投入所需的最小能量 N 垃圾桶里的垃圾。
约束
- 1 \leq N \leq 2 \times 10^{5}
- 0 < x_1 < ... < x_N \leq 10^9
- 1 \leq X \leq 10^9
- 输入中的所有值都是整数。
部分分数
- 400 通过满足以下条件的测试集将获得积分 N \leq 2000.
输入
输入由标准输入按以下格式给出:
N X
x_1 x_2 ... x_{N}
输出
打印答案。
示例输入 1
2 100 1 10
示例输出 1
355
- 行驶至位置 10 通过消费 10 能量点。
- 通过消耗捡起一块垃圾 100 能量点。
- 行驶至位置 1 通过消费 36 能量点。
- 通过消耗捡起一块垃圾 100 能量点。
- 行驶至位置 0 通过消费 9 能量点。
- 通过食用将两件垃圾放入垃圾桶 100 能量点。
该策略总共消耗 10+100+36+100+9+100=355 能量点。
示例输入 2
5 1 1 999999997 999999998 999999999 1000000000
示例输出 2
19999999983
示例输入 3
10 8851025 38 87 668 3175 22601 65499 90236 790604 4290609 4894746
示例输出 3
150710136
示例输入 4
16 10 1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408
示例输出 4
3256017715