/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
すぬけ君は掃除ロボットを使って部屋を掃除することにしました。
数直線上に N 個のゴミが落ちています。 左から i 番目のゴミは位置 x_i にあります。 これらのゴミを位置 0 にあるゴミ箱に入れたいです。
ゴミの位置に関して、0 < x_1 < x_2 < ... < x_{N} \leq 10^{9} が成立します。
掃除ロボットははじめ位置 0 にいます。ロボットは数直線上を自由に動くことができ、ゴミのある位置にいくとゴミを拾うことができます。 ゴミは同時に何個でも運ぶことでき、ゴミ箱の位置に行くとゴミをゴミ箱に入れることができます。ゴミをゴミ箱以外の場所に置くことは許されません。
ロボットがゴミを拾う、あるいは(1 個以上の)ゴミをゴミ箱に入れるとき X だけエネルギーを消費します。ゴミをゴミ箱に入れるときに消費するエネルギーはゴミの個数にかかわらず X です。 また、ロボットが k 個のゴミを運んでいるとき、距離 1 だけ移動するのに (k+1)^{2} だけエネルギーを消費します。
N 個のゴミを全てゴミ箱に入れるために必要なエネルギーの最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^{5}
- 0 < x_1 < ... < x_N \leq 10^9
- 1 \leq X \leq 10^9
- 与えられる入力は全て整数
部分点
- N \leq 2000 を満たすデータセットに正解した場合、400 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N X
x_1 x_2 ... x_{N}
出力
答えを出力せよ。
入力例 1
2 100 1 10
出力例 1
355
- 10 のエネルギーを消費して、位置 10 に移動する
- 100 のエネルギーを消費して、ゴミを取る
- 36 のエネルギーを消費して、位置 1 に移動する
- 100 のエネルギーを消費して、ゴミを取る
- 9 のエネルギーを消費して、位置 0 に移動する
- 100 のエネルギーを消費して、2 つのゴミをゴミ箱に入れる
このように行動したとき、消費したエネルギーは 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
Score : 700 points
Problem Statement
Snuke has decided to use a robot to clean his room.
There are N pieces of trash on a number line. The i-th piece from the left is at position x_i. We would like to put all of them in a trash bin at position 0.
For the positions of the pieces of trash, 0 < x_1 < x_2 < ... < x_{N} \leq 10^{9} holds.
The robot is initially at position 0. It can freely move left and right along the number line, pick up a piece of trash when it comes to the position of that piece, carry any number of pieces of trash and put them in the trash bin when it comes to position 0. It is not allowed to put pieces of trash anywhere except in the trash bin.
The robot consumes X points of energy when the robot picks up a piece of trash, or put pieces of trash in the trash bin. (Putting any number of pieces of trash in the trash bin consumes X points of energy.) Also, the robot consumes (k+1)^{2} points of energy to travel by a distance of 1 when the robot is carrying k pieces of trash.
Find the minimum amount of energy required to put all the N pieces of trash in the trash bin.
Constraints
- 1 \leq N \leq 2 \times 10^{5}
- 0 < x_1 < ... < x_N \leq 10^9
- 1 \leq X \leq 10^9
- All values in input are integers.
Partial Scores
- 400 points will be awarded for passing the test set satisfying N \leq 2000.
Input
Input is given from Standard Input in the following format:
N X
x_1 x_2 ... x_{N}
Output
Print the answer.
Sample Input 1
2 100 1 10
Sample Output 1
355
- Travel to position 10 by consuming 10 points of energy.
- Pick up the piece of trash by consuming 100 points of energy.
- Travel to position 1 by consuming 36 points of energy.
- Pick up the piece of trash by consuming 100 points of energy.
- Travel to position 0 by consuming 9 points of energy.
- Put the two pieces of trash in the trash bin by consuming 100 points of energy.
This strategy consumes a total of 10+100+36+100+9+100=355 points of energy.
Sample Input 2
5 1 1 999999997 999999998 999999999 1000000000
Sample Output 2
19999999983
Sample Input 3
10 8851025 38 87 668 3175 22601 65499 90236 790604 4290609 4894746
Sample Output 3
150710136
Sample Input 4
16 10 1 7 12 27 52 75 731 13856 395504 534840 1276551 2356789 9384806 19108104 82684732 535447408
Sample Output 4
3256017715