Informatica Online Judge

  카드 점수 게임 [2094 / 082E]

Time Limit(Test case) : 300(ms)
Number of users who solved : 8   Total Tried : 8


The Champion of this Problem (C++) : gs16109 - 0ms / 133byte
My Best Submission (C++) : N/A

[AtCoder]

Background

각각의 카드에 수가 적인 $N$ 장의 카드 더미가 있다.

위로부터 $i$번째 카드에 적힌 수는 $a_i$이다.

경곽이와 영재는 둘이서 카드 점수 게임을 시작한다.

처음에 경곽이는 수 $X$가 적힌 카드를 들고 있고, 영재는 $Y$가 적힌 카드를 들고 있다.

그리고 경곽이로부터 시작하여 서로 다음과 같은 규칙으로 게임을 진행한다.

- 카드 더미의 위로부터 1장 이상의 카드를 가지고 올 수 있다. 그리고 원래 가지고 있던 카드를 버리고 마지막으로 들고온 카드를 자기 카드로 한다.

(카드 더미의 모든 카드에 적혀있는 수들은 경곽이와 영재 모두 알고있다.)

카드 더미에 카드가 없어질 때까지 이 작업을 반복한다.

게임의 점수는 경곽이와 영재가 게임이 종료된 후 가지고 있는 카드에 쓰여있는 수의 차이로 한다. (차이는 항상 절댓값이다.)

그런데 경곽이는 이 게임의 점수를 최대화하기를 원하고, 영재는 이 게임의 점수를 최소화하기를 원한다.

둘 다 최선을 다해서 게임에 임할 때, 얻을 수 있는 점수는 몇 점인지 구하시오.

Input

$N~~X~~Y$
$a_1~~a_2~~...~~a_N$

[입력값의 정의역]

$1 ≤ N ≤ 4,000$
$1 ≤ x,~y,~a_i ≤ 10^9$

Output

구한 점수를 출력한다.

IO Example

입력1
3 100 100
10 1000 100

출력1
900

* 설명 : 경곽이가 10, 1000 2장의 카드를 들고 가면 1000이 되고 영재는 100을 들고가게 된다. 따라서 차이는 900이 된다.

입력2
5 1 1
1 1 1 1 1

출력2
0

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]