아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

이동하며 풀 뜯기

시간 제한1초메모리 제한128 MB

요약
소 Bessie가 위치 L에서 출발해 직선 위 N개의 풀더미를 모두 먹을 때, 각 더미를 먹는 시각의 합을 최소로 만든다.
난이도

보통10점 중 6점

유형
동적 계획법, 구간, 그리디
정답자
아직 제출이 없습니다

문제

길게 뻗은 일직선 목초지를 수직선이라고 생각하자. 이 수직선 위의 서로 다른 정수 위치에 풀 더미가 NN개 있다 (1≤N≤10001 \le N \le 1000). 각 풀 더미는 수직선 위의 한 점으로 본다.

젖소 베시는 수직선 위의 정수 위치 LL (1≤L≤1,000,0001 \le L \le 1{,}000{,}000)에서 출발하여, 왼쪽과 오른쪽 어느 방향으로든 자유롭게 (필요하면 방향을 바꿔 가며) 움직이면서 모든 풀 더미를 먹는다. 이동 속도는 일정하여 시간 한 단위 동안 거리 한 단위를 움직이며, 풀 더미가 있는 위치에 도달하는 즉시 그 풀 더미를 먹는다.

한동안 먹히지 않은 풀 더미는 시들어 간다. 어떤 풀 더미의 시듦(staleness) 은 베시가 움직이기 시작한 시각부터 그 풀 더미를 먹는 시각까지 흐른 시간으로 정의한다. 베시는 모든 풀 더미의 시듦의 총합을 최소로 만들고 싶다.

모든 풀 더미를 다 먹었을 때 얻을 수 있는 시듦 총합의 최솟값을 구하여라.

입력

첫째 줄에 두 정수 NN과 LL이 공백으로 구분되어 주어진다.

다음 NN개의 줄에는 각 줄마다 풀 더미의 위치 PP (1≤P≤1,000,0001 \le P \le 1{,}000{,}000)가 하나씩 주어진다. 모든 위치는 서로 다르다.

출력

모든 풀 더미를 먹었을 때 얻을 수 있는 시듦 총합의 최솟값을 한 줄에 출력한다.

예제1

  1. 예제 1

    입력
    4 10
    1
    9
    11
    19
    
    예상 출력
    44