시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 256 | 30 | 26 | 11.404% |
ALPS 부원들은 친목 도모를 위해 다 같이 알프스 산맥으로 여행을 떠났다! 알프스 산맥은 $N$개의 산이 겹치거나 빈 부분 없이 일렬로 나열된 형태이며, 왼쪽에서부터 $i$번째에 위치한 산은 빗변을 아래로 하며 높이가 $H_i$인 직각 이등변 삼각형이다.
ALPS 부원들은 체력이 좋지 않기 때문에 $1$번 산에서 시작해 $N$번 산에서 끝나는 케이블카 노선을 설치해 산을 오르려 한다. 노선을 설치하는 법은 다음과 같다.
각 와이어의 설치 비용은 설치해야 할 와이어 길이의 제곱과 같으며 노선의 설치 비용은 사용한 와이어의 설치 비용의 합이다. ALPS 부원들을 위해 최대 $K$개의 와이어를 사용하여 $1$번 산에서 시작해 $N$번 산에서 끝나는 노선을 설치하기 위한 최소 비용을 구해보자.
첫 번째 줄에 알프스 산맥을 이루는 산의 수 $N$과 사용할 와이어의 개수 $K$가 주어진다. $(2 \leq N \leq 50\,000;$ $1 \leq K \leq N-1)$
두 번째 줄에 각 산의 높이 $H_1, H_2, \cdots, H_N$이 공백으로 구분되어 정수로 주어진다. $(1 \leq H_i \leq 100)$
최대 $K$개의 와이어를 사용해 $1$번 산에서 시작해 $N$번 산에서 끝나는 노선을 설치하기 위한 최소 비용을 출력한다.
4 2 4 2 3 4
172