102187: [AtCoder]ABC218 H - Red and Blue Lamps

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

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

Input

题意翻译

## 题意翻译 现在你有 $N$ 盏灯排成一列,编号为 $1$ 到 $N$。对于任意一盏灯,你可以将其变成红色或蓝色。你想让其中的 $R$ 盏灯变成红色,$N-R$ 盏灯变成蓝色。 当第 $i$ 和 $i+1$ 盏灯以不同的颜色发光时,你将获得 $A_i$ 点报酬。 请你计算当有 $R$ 盏灯为红色,$N-R$ 盏灯为蓝色时,你所获得的报酬和的最大值。

Output

分数:$600$分

问题描述

有一排编号为$1$到$N$的$N$盏灯。你需要将其中的$R$盏灯点亮为红色,其余的灯点亮为蓝色。

对于每$i=1,\ldots,N-1$,如果灯$i$和灯$i+1$点亮的颜色不同,将会获得奖励$A_i$。

通过高效地决定灯的颜色,找出可以获得的最大总奖励。

约束条件

  • $2 \leq N \leq 2\times 10^5$
  • $1 \leq R \leq N-1$
  • $1 \leq A_i \leq 10^9$
  • 输入中的所有值都是整数。

输入

从标准输入中按照以下格式获取输入:

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

输出

打印答案。


样例输入1

6 2
3 1 4 1 5

样例输出1

11

将灯$3, 5$点亮为红色,将灯$1, 2, 4, 6$点亮为蓝色,可以获得总奖励$A_2+A_3+A_4+A_5=11$。

你无法获得更多的奖励,所以答案是$11$。


样例输入2

7 6
2 7 1 8 2 8

样例输出2

10

将灯$1, 2, 3, 4, 5, 7$点亮为红色,将灯$6$点亮为蓝色,可以获得总奖励$A_5+A_6=10$。


样例输入3

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

样例输出3

46207983

加入题单

上一题 下一题 算法标签: