/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
1 から N の番号がついた N 個のランプが一列に並べられています。あなたはこのうち R 個を赤く、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
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