Score : $600$ points
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.
Input is given from Standard Input in the following format:
$N$ $R$ $A_1$ $A_2$ $\ldots$ $A_{N-1}$
Print the answer.
6 2 3 1 4 1 5
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$.
7 6 2 7 1 8 2 8
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$.
11 7 12345 678 90123 45678901 234567 89012 3456 78901 23456 7890
46207983