問題一覧 > 通常問題

No.2028 Even Choice

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 130
作問者 : Shirotsume / テスター : 👑 ygussany とりゐ
9 ProblemId : 8187 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-08-05 19:47:26

問題文

NN 枚のカードが横一列に並んでいます。初め、左から ii 番目 (1≤i≤N)(1 \leq i \leq N) のカードには、整数 AiA_i が書かれています。あなたは、以下の操作をちょうど KK 回行います。

  • 現時点で残っているカードの枚数を MM とする。 1≤i≤M1 \leq i \leq M を満たす 偶数 ii を選び、残ったカードの中で左から ii 番目にあるものを取り除く。

操作を KK 回行った後、取り除いた KK 枚のカードに書かれた整数の総和として考えられる最大値を求めてください。

制約

  • 入力は全て整数
  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤K≤N−11 \leq K \leq N - 1
  • 1≤Ai≤1091 \leq A_i \leq 10^9 (1≤i≤N)(1 \leq i \leq N)

入力

入力は標準入力から以下の形式で与えられる。

NN KK
A1A_1 A2A_2 …\dots ANA_N

出力

取り除いた KK 枚のカードに書かれた整数の総和として考えられる最大値を出力せよ。最後に改行すること。

サンプル

サンプル1
入力
5 3
3 1 4 1 5
出力
10

操作を以下のように行うと、取り除いたカードに書かれている整数の総和を 1010 にできます。

  • 1回目:残っているカードは (3,1,4,1,5)(3, 1, 4, 1, 5) である。左から 22 番目のカードを取り除く。
  • 2回目:残っているカードは (3,4,1,5)(3, 4, 1, 5) である。左から 44 番目のカードを取り除く。
  • 3回目:残っているカードは (3,4,1)(3, 4, 1) である。左から 22 番目のカードを取り除く。

整数の総和が 1010 より大きくなるような操作はできません。

サンプル2
入力
4 2
1 2 3 4
出力
6

サンプル3
入力
15 9
883548341 954946168 431651126 981968995 420220260 985870634 94232609 265487324 775722477 261574734 187926860 707452572 931578547 977913086 935287414
出力
7682391019

出力は 32bit 整数に収まらない可能性があります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。