시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (추가 시간 없음) 1024 MB 39 19 18 64.286%

문제

A street named Fascination Street is divided into $N$ equal length of blocks. For each block $i$ ($1 \leq i \leq N$), it has block $i-1$ in its left side if $i > 1$, and block $i+1$ in its right side if $i < N$.

Unlike its name, the street is infamous to be a dark and eerie place in the night. To solve this, Robert decided to install the streetlight for some of the blocks. The cost of installing a streetlight for $i$-th block is $W_i$, and the total cost is the sum of each installation cost. After installing, every block should either have a streetlight, or have a streetlight in its left or right block.

Robert also has some tricks to reduce the cost. Before installing the streetlight, Robert selects two distinct blocks $i$ and $j$, and exchange their position. After the operation, the cost of installation is exchanged. In other words, the operation simply swaps the value of $W_i$ and $W_j$. This operation have no cost, but Robert can only perform it at most $K$ times.

Now, given the array $W$ and the maximum possible number of operations $K$, you should find the minimum cost of lighting the whole street.

입력

The first line contains two space-separated integers $N,\ K$. $N$ is the number of blocks, and $K$ is the maximum possible number of operations. ($1 \leq N \leq 250000, \ 0 \leq K \leq 9$)

The second line contains $N$ space-separated integers $W_1$, $W_2$, $\cdots$, $W_N$, where $W_i$ is the cost of installing a streetlight for $i$-th block. ($0 \leq W_i \leq 10^9$)

출력

Print a single integer which contains the minimum cost of lighting the whole street.

예제 입력 1

5 0
1 3 10 3 1

예제 출력 1

4

예제 입력 2

5 1
1 3 10 3 1

예제 출력 2

2

예제 입력 3

12 0
317 448 258 208 284 248 315 367 562 500 426 390

예제 출력 3

1525

예제 입력 4

12 2
317 448 258 208 284 248 315 367 562 500 426 390

예제 출력 4

1107

출처

University > KAIST > 2018 KAIST 8th ACM-ICPC Mock Competition E번

  • 문제의 오타를 찾은 사람: jh05013
  • 문제를 만든 사람: koosaga