No.2856 Junk Market Game
タグ : / 解いたユーザー数 74
作問者 :
sepa38
Problem Statement
At MMA's junk market, $2N$ items are on sale, $1$ of each.
The $i$-th item can be purchased by a general customer for $A_i$ yen, and by an MMA member for $B_i$ yen.
A general customer and an MMA member play a game. With the general customer going first and the MMA member going second, they alternately repeat the following operation.
- Choose $1$ item of the junk market that has not been purchased yet, and purchase it.
The game ends when all items of the junk market have been purchased.
Let $X$ be the amount paid by the general customer and $Y$ be the amount paid by the MMA member. The general customer tries to minimize $X - Y$, and the MMA member tries to maximize $X - Y$.
Find the value of $X - Y$ when both act optimally.
Constraints
- $1 \leq N \leq 1000$
- $1 \leq A_i, B_i \leq 10^{9}$
- All inputs are integers.
Input
The input is given from standard input in the following format.
$N$
$A_1$ $A_2$ ... $A_{2N}$
$B_1$ $B_2$ ... $B_{2N}$
Output
Output the answer to the problem on one line.
Sample
Sample 1
Input
1 100 200 150 300
Output
-200
If the general customer purchases the $1$st item, the MMA member has no choice but to purchase the $2$nd item, so $X - Y = 100 - 300 = -200$.
Sample 2
Input
3 100 200 350 400 550 600 400 200 300 100 150 500
Output
-50
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。