問題一覧 > 通常問題

No.1522 Unfairness

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 55
作問者 : aspiaspi / テスター : NatsubiSoganNatsubiSogan nok0nok0 NachiaNachia
6 ProblemId : 6064 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-17 00:10:31

問題文

長さ $N$ の整数列 $A=(A_1,A_2, \cdots , A_N)$ が与えられます。

あなたはまず、 $2k \leq N$ を満たす非負整数 $k$ を選びます。そして、$A$ から $2k$ 個の要素を任意に選択します。

選択した $2k$ 個の整数について、不平等さを以下のように定義します。

  • 選択した $2k$ 個の整数を値の降順に並び替えた数列を $B=(B_1,B_2, \cdots ,B_{2k})$ とする。
  • $B$ の奇数番目の要素の総和、すなわち $\sum_{i=1}^{k} B_{2i-1}$ を $O$ とする。
  • $B$ の偶数番目の要素の総和、すなわち $\sum_{i=1}^{k} B_{2i}$ を $E$ とする。
  • 不平等さは $O-E$ である。

不平等さが $M$ 以下になるよう適切に要素を選択したとき、$O$ は最大でいくつになるでしょうか。

入力

$N\ M$
$A_{1}\ A_{2}\ \ldots \ A_{N}$
  • 入力はすべて整数
  • $2 \leq N \leq 3000$
  • $0 \leq M \leq 3000$
  • $0 \leq A_i \leq 10^6$

出力

問題文の条件の下での $O$ の最大値を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
6 3
1 1 2 3 5 8
出力
9

$k=2$ として、$A_1,A_2,A_5,A_6$ を選ぶのが最適です。この場合、$B=(8,5,1,1)$ となり、不平等さは $(8+1)-(5+1)=3$ です。$O$ が $9$ を上回ることはありません。

なお、全要素を選んでしまうと不平等さは $4$ となってしまいます。

サンプル2
入力
7 7
7 7 7 7 7 7 7
出力
21

どのような選び方をとっても不平等さは $0$ です。よって、 $6$ つの要素を選択することで $O$ を最大化できます。選ぶ要素は偶数個であることに注意してください。

サンプル3
入力
5 15
31 41 59 26 53
出力
90

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