問題一覧 > 通常問題

No.1522 Unfairness

レベル : / AI推定難易度 : 1675 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 73
作問者 : aspi / テスター : NatsubiSogan nok0 👑 Nachia
お気に入りにしたユーザー ProblemId : 6064 / 自分の提出
問題文最終更新日: 2021-05-17 00:10:31
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 297 (順位表) の他の問題:

Problem Statement

You are given an integer sequence $A=(A_1,A_2, \cdots , A_N)$ of length $N$.

First, you choose a non-negative integer $k$ satisfying $2k \leq N$. Then, you choose any $2k$ elements from $A$.

For the $2k$ chosen integers, the unfairness is defined as follows.

  • Let $B=(B_1,B_2, \cdots ,B_{2k})$ be the sequence obtained by sorting the $2k$ chosen integers in descending order of value.
  • Let $O$ be the sum of the odd-indexed elements of $B$, that is, $\sum_{i=1}^{k} B_{2i-1}$.
  • Let $E$ be the sum of the even-indexed elements of $B$, that is, $\sum_{i=1}^{k} B_{2i}$.
  • The unfairness is $O-E$.

When you choose the elements appropriately so that the unfairness is at most $M$, what is the maximum possible value of $O$?

Input

$N\ M$
$A_{1}\ A_{2}\ \ldots \ A_{N}$
  • All inputs are integers.
  • $2 \leq N \leq 3000$
  • $0 \leq M \leq 3000$
  • $0 \leq A_i \leq 10^6$

Output

Output the maximum value of $O$ under the conditions in the problem statement.

Print a newline at the end.

Sample

Sample 1
Input
6 3
1 1 2 3 5 8
Output
9

It is optimal to take $k=2$ and choose $A_1,A_2,A_5,A_6$. In this case, $B=(8,5,1,1)$, and the unfairness is $(8+1)-(5+1)=3$. $O$ can never exceed $9$.

Note that if you choose all the elements, the unfairness becomes $4$.

Sample 2
Input
7 7
7 7 7 7 7 7 7
Output
21

The unfairness is $0$ no matter how you choose. Therefore, $O$ can be maximized by choosing $6$ elements. Note that the number of chosen elements must be even.

Sample 3
Input
5 15
31 41 59 26 53
Output
90

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