Score : $600$ points

问题描述

有 $N$ 盏灯，编号为从 $1$ 到 $N$ ，它们排成一行。你需要将其中 $R$ 盏灯点亮为红色，其余 $N-R$ 盏灯点亮为蓝色。

对于每个 $i=1,\ldots,N-1$ ，如果第 $i$ 盏灯与第 $i+1$ 盏灯的颜色不同，则会获得奖励 $A_i$ 。

请确定通过有效决策灯具颜色可以获得的最大总奖励。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ lamps numbered $1$ through $N$ arranged in a row. You are going to light $R$ of them in red and $N-R$ in blue.

For each $i=1,\ldots,N-1$, a reward of $A_i$ is given if Lamp $i$ and Lamp $i+1$ light up in different colors.

Find the maximum total reward that can be obtained by efficiently deciding the colors of the lamps.

Constraints

• $2 \leq N \leq 2\times 10^5$
• $1 \leq R \leq N-1$
• $1 \leq A_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $R$

$A_1$ $A_2$ $\ldots$ $A_{N-1}$

Output

Print the answer.

Sample Input 1

6 2
3 1 4 1 5

Sample Output 1

11

Lighting up Lamps $3, 5$ in red and Lamps $1, 2, 4, 6$ in blue yields a total reward of $A_2+A_3+A_4+A_5=11$.

You cannot get any more, so the answer is $11$.

Sample Input 2

7 6
2 7 1 8 2 8

Sample Output 2

10

Lighting up Lamps $1, 2, 3, 4, 5, 7$ in red and Lamp $6$ in blue yields a total reward of $A_5+A_6=10$.

Sample Input 3

11 7
12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

Sample Output 3

46207983

update @ 2024/3/10 09:39:57