No.1522 Unfairness
タグ : / 解いたユーザー数 72
作問者 :
aspi
/ テスター :
NatsubiSogan
nok0
👑 
Nachia
問題文
長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。