Informatica Online Judge

  청소 로봇 [2277 / 08E5]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : gs15120 - 0ms / 1399byte
My Best Submission (C++) : N/A

[AGC27]

Background

경곽이는 청소로봇을 이용해서 청소를 하기로 했다.

수직선 상에 $N$개의 쓰레기가 위치하고 있다. 왼쪽으로부터 $i$번째 쓰레기의 위치는 $x_i$이다.

이들 쓰레기들을 위치 $0$에 있는 쓰레기통에 모두 넣고자 한다.

쓰레기의 위치에 대해서는 $0 < x_1 < ... < x_N ≤ 10^9$을 만족한다.

청소로봇은 처음에 위치 $0$에 위치하고 있다.

로봇은 수직선 상을 자유롭게 돌아다닐 수 있으며, 쓰레기의 위치로 가면 쓰레기를 수거할 수 있다.

쓰레기는 동시에 여러 개를 운발할 수도 있다. 쓰레기 통의 위치에 도달하면 가지고 있는 모든 쓰레기를 처리할 수 있다.

쓰레기를 쓰레기통 이외의 위치에는 둘 수 없다.

로봇이 쓰레기를 줍거나 쓰레기 통에 1개 이상의 쓰레기를 넣을 때 $X$의 에너지를 소비한다.

쓰레기를 쓰레기 통에 넣을 때 드는 에너지는 개수에 관계없이 항상 $X$를 소비한다.

또 로봇이 $k$개의 쓰레기를 운반하고 있을 때, 거리 1당 $(k+1)^2$만큼의 에너지를 소비한다.

$N$개의 쓰레기를 모두 쓰레기 통에 넣기 위해서 필요한 최소 에너지를 구하시오.

Input

첫 번재 줄에 $N$, $X$가 공백으로 구분되어 입력된다.

다음 줄에 $x_1$부터 $x_N$의 값이 공백으로 구분되어 입력된다.

[입력값의 정의역]

$1≤N≤200,000$
$0 < x_1 < ... < x_N ≤ 10^9$
$1 ≤ X ≤ 10^9$

Output

청소를 마치는데 드는 최소 에너지를 출력한다.

IO Example

입력
2 100
1 10

출력
355

* 설명
- 에너지 10을 써서 위치 10으로 이동한다.
- 100의 에너지를 써서 쓰레기를 줍는다.
- 36의 에너지를 써서 위치 1로 이동한다.
- 100의 에너지를 써서 쓰레기를 줍는다.
- 9의 에너지를 써서 위치 0으로 이동한다.
- 100의 에너지를 써서 2개의 쓰레기를 버린다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]