문제 번호 1049 --점프3

1049: 점프3

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 19  해결 문제 수: 11
[제출][채점 상황 열람][게시판][:]

문제 설명

$1,2,…,N$ 까지 번호가 붙은 돌이 있다. $i$ 번째 돌은 높이 $h_i$를 가진다.

초기에 경곽이는 $1$번 돌에 위치해 있다. $N$ 번째 돌에 도착하기 위해 다음 동작을 반복한다.

  • 현재 $i$ 번째 돌에 위치해있다면 $i+1$,$i+2$,$…$,$N$ 로 점프할 수 있으며 이때의 비용은 $|h_i−h_j|^2 + C$ 이 발생하며 $j$는 새롭게 도착한 위치이다.

$N$에 도달하기 위한 최소의 비용을 출력하라.

입력

$N$ $C$

$h_1$ $h_2$ $...$ $h_N$

  • $2≤N≤2*10^5$
  • $1≤C≤10^{12}$
  • $1≤h_1 < h2 < ... < h_N <= 10^6$

출력

$N$에 도달하기 위한 최소의 비용을 출력하라.

입력 예시

5 6
1 2 3 4 5

출력 예시

20

도움말

출처

 
[제출][채점 상황 열람]