No.2028 Even Choice
タグ : / 解いたユーザー数 130
作問者 :
Shirotsume
/ テスター :
ygussany
とりゐ
Problem Statement
$N$ cards are arranged in a horizontal row. Initially, the $i$-th card from the left $(1 \leq i \leq N)$ has the integer $A_i$ written on it. You perform the following operation exactly $K$ times.
- Let $M$ be the number of cards currently remaining. Choose an even number $i$ satisfying $1 \leq i \leq M$, and remove the $i$-th card from the left among the remaining cards.
Find the maximum possible value of the sum of the integers written on the $K$ cards removed after performing the operation $K$ times.
Constraints
- All inputs are integers
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq K \leq N - 1$
- $1 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
Input
The input is given from standard input in the following format.
$N$ $K$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the maximum possible value of the sum of the integers written on the $K$ removed cards. Print a newline at the end.
Sample
Sample 1
Input
5 3 3 1 4 1 5
Output
10
By performing the operations as follows, the sum of the integers written on the removed cards can be made $10$.
- 1st operation: The remaining cards are $(3, 1, 4, 1, 5)$. Remove the $2$-nd card from the left.
- 2nd operation: The remaining cards are $(3, 4, 1, 5)$. Remove the $4$-th card from the left.
- 3rd operation: The remaining cards are $(3, 4, 1)$. Remove the $2$-nd card from the left.
No sequence of operations can make the sum of the integers greater than $10$.
Sample 2
Input
4 2 1 2 3 4
Output
6
Sample 3
Input
15 9 883548341 954946168 431651126 981968995 420220260 985870634 94232609 265487324 775722477 261574734 187926860 707452572 931578547 977913086 935287414
Output
7682391019
The output may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。