D - 1 or 2

Contest Duration: 2021-05-29(Sat) 12:00 - 2021-05-29(Sat) 14:00 (local time) (120 minutes) Back to Home

D - 1 or 2 Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $700$ 点

問題文

すぬけ君は黒板と $N$ 個の飴を持っています。 $i$ 番目の飴の おいしさ は $a_i$ です。

すぬけ君は手持ちの飴がなくなるまで、以下の操作を繰り返します。

手持ちの飴から $1$ つ、あるいは $2$ つ選んで食べ、その後選んだ飴のおいしさの総和を黒板に書き込む(食べた飴はなくなります)。

すぬけ君は黒板に書かれた値の最大値を $X$ 、最小値を $Y$ として $X-Y$ が最小になるようにしたいです。 $X-Y$ としてありうる値の最小値を求めてください。

制約

与えられる入力は全て整数
$1 \leq N \leq 5000$
$-10^{9} \leq a_i \leq 10^9$

入力

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

 $N$ 
 $a_{1}$   $a_{2}$   $\cdots$   $a_N$

出力

黒板に書かれた値の最大値を $X$ 、最小値を $Y$ とする。 $X-Y$ としてありうる値の最小値を出力せよ。

入力例 1Copy

Copy

3
1 2 4

出力例 1Copy

Copy

$1$ 回目の操作で美味しさ $1,2$ の飴を食べ、 $2$ 回目の操作で美味しさ $4$ の飴を食べるのが最適な操作手順の $1$ つです。

入力例 2Copy

Copy

2
-100 -50

出力例 2Copy

Copy

$1$ 回目の操作で美味しさ $-100,-50$ の飴を食べるのが最適です。

入力例 3Copy

Copy

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

出力例 3Copy

Copy

Score : $700$ points

Problem Statement

Snuke has a blackboard and $N$ candies. The tastiness of the $i$ -th candy is $a_i$ .

He will repeat the operation below until he has no more candy.

Choose one or two of his candies and eat them (of course, they disappear). Then, write on the blackboard the total tastiness of the candies he has just chosen.

Snuke wants to minimize $X-Y$ , where $X$ and $Y$ are the largest and smallest values written on the blackboard, respectively. Find the minimum possible value of $X-Y$ .

Constraints

All values in input are integers.
$1 \leq N \leq 5000$
$-10^{9} \leq a_i \leq 10^9$

Input

Input is given from Standard Input in the following format:

 $N$ 
 $a_{1}$   $a_{2}$   $\cdots$   $a_N$

Output

Print the minimum possible value of $X-Y$ , where $X$ and $Y$ are the largest and smallest values written on the blackboard, respectively.

Sample Input 1Copy

Copy

3
1 2 4

Sample Output 1Copy

Copy

One optimal sequence of operations is to eat the candies with the tastinesses of $1$ and $2$ in the first operation, and then eat the candies with the tastiness of $4$ in the second operation.

Sample Input 2Copy

Copy

2
-100 -50

Sample Output 2Copy

Copy

It is optimal to eat both candies with the tastiness of $-100$ and $-50$ in the first operation.

Sample Input 3Copy

Copy

20
-18 31 -16 12 -44 -5 24 17 -37 -31 46 -24 -2 11 32 16 0 -39 35 38

Sample Output 3Copy

Copy