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