Informatica Online Judge

  도박 #3 [1788 / 06FC]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 90   Total Tried : 125


The Champion of this Problem (C++) : gs16051 - ms / 353byte
My Best Submission (C++) : N/A

[koistudy.net (34st 백윤기)]

Background

$A$는 빚이 산더미여서 금방이라도 파산할 위기에 놓여있다. 그래서 그는 이번 도박에서 최대한 많은 돈을 따야 빚을 갚을 수 있다.

$A$는 카지노 딜러와 게임을 하여 돈을 얻고자 한다.

$A$와 딜러는 각각 $N$장의 카드를 가지고 있다. 총 $2N$ 장의 카드에는 숫자가 적혀져 있다.

총 $N$회에 걸쳐 게임을 진행하려고 하는데, $A$와 딜러는 각 회마다 카드를 $1$장씩 낸다.

$A$가 낸 카드의 숫자가 더 크다면, $A$는 그 숫자만큼의 돈을 얻을 수 있다.

$A$는 전날 카지노에 잠입해, 딜러가 낼 카드의 숫자와, 딜러가 어떤 순서로 카드를 낼 것인지 미리 알아냈다.

이 정보를 바탕으로, $A$가 내일 얻을 최대 금액을 알아보자.

Input

한 사람당 가지고 있는 카드의 장수 $N$이 입력된다.

두 번째 줄에는 딜러가 낼 카드의 순서로 $N$개의 숫자가 입력된다.

세 번째 줄에는 $A$가 현재 가지고 있는 카드 $N$장이 입력된다.

(카드에 적힌 수는 $50,000$ 이하다)

[입력값의 정의역]
Subtask #1 : $N = 2$
Subtask #2 : $N <= 10$
Subtask #3 : $N <= 5,000$
Subtask #4 : $N <= 100,000$

Output

첫째 줄에는 $A$가 얻는 최대 액수를 출력한다.

IO Example

입력1
3
6 1 3
1 2 7

출력1
9

설명 : $A$가 카드를 $7$, $2$, $1$ 순으로 내면 1회전과 2회전에서 각각 $7$원, $2$원을 얻는다.

입력2
7
10 3 23 6 9 12 1
20 2 18 3 2 1 1

출력2
41

설명 : $A$가 카드를 $18$, $2$, $2$, $1$, $1$, $20$, $3$ 순으로 내면 1회전에서 $18$원, 6회전에서 $20$원, 7회전에서 $3$원을 얻는다.

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