AT_abc218_h [ABC218H] Red and Blue Lamps

题目描述

有 $N$ 个编号为 $1$ 到 $N$ 的灯泡排成一行。你打算将其中 $R$ 个灯泡点亮为红色，其余 $N-R$ 个点亮为蓝色。

对于每个 $i=1,\ldots,N-1$，如果灯泡 $i$ 和灯泡 $i+1$ 的颜色不同，你可以获得 $A_i$ 的奖励。

请你通过合理安排每个灯泡的颜色，使得可以获得的奖励总和最大，并输出该最大值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出最大可能获得的奖励总和。

输入输出样例 #1

输入 #1

6 2
3 1 4 1 5

输出 #1

11

输入输出样例 #2

输入 #2

7 6
2 7 1 8 2 8

输出 #2

10

输入输出样例 #3

输入 #3

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

输出 #3

46207983

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq R \leq N-1$
• $1 \leq A_i \leq 10^9$
• 输入的所有数值均为整数

样例解释 1

将第 $3$、$5$ 号灯泡点亮为红色，将第 $1$、$2$、$4$、$6$ 号灯泡点亮为蓝色，可以获得 $A_2+A_3+A_4+A_5=11$ 的奖励。无法获得更高的奖励，因此答案为 $11$。

样例解释 2

将第 $1$、$2$、$3$、$4$、$5$、$7$ 号灯泡点亮为红色，将第 $6$ 号灯泡点亮为蓝色，可以获得 $A_5+A_6=10$ 的奖励。

由 ChatGPT 4.1 翻译