← 返回题目列表

AtCoder · agc027_b

B. 垃圾收集器

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

分数: 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