카드 Batch 컴파일 명령
| 시간 제한 | 메모리 제한 | 제출 횟수 | 통과한 사람 수 | 비율 |
|---|---|---|---|---|
| 1000 ms | 32 MiB | 40 | 35 | 87.5% |
승현이는 앞면과 뒷면이 있는 카드 $n$장을 가지고 있습니다. 각 카드의 앞면에는 1 이상 2222 이하의 정수가 적혀 있으며, 이 수는 카드마다 서로 다릅니다. 각 카드의 뒷면에는 동물 그림이 그려져 있으며, 이 그림 역시 카드마다 서로 다릅니다.
<small>가능한 카드의 예시입니다. 왼쪽 그림은 앞면, 오른쪽 그림은 뒷면입니다.</small>
승현이는 카드들을 바닥에 뒷면이 보이도록 일렬로 늘어 놓고, 차례대로 1 이상 $n$ 이하의 자연수 번호를 붙였습니다. 이 중 $i$번 카드의 앞면에 적혀 있는 수를 $c_{i}$로 둡시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 아래와 같은 행동을 반복합니다.
- 승현이는 마음에 드는 서로 다른 카드 두 장을 앞면이 보이도록 뒤집어 봅니다.
- 승현이는 앞면에 더 작은 수가 적혀 있는 카드를 주머니 속에 넣고, 더 큰 수가 적혀 있는 카드는 다시 바닥에 뒷면이 보이도록 내려놓습니다.
- 카드가 두 장 이상 남았다면 1번으로 돌아갑니다. 카드가 정확히 한 장 남았다면, 승현이는 주머니 속에 있는 카드들을 꺼내 앞면에 적혀 있는 수들의 합을 구합니다.
승현이는 큰 수가 좋아서, 마지막에 주머니 속에 들어있는 카드들에 적혀 있는 수들의 합을 가능한 한 크게 하고자 합니다. (뒷면에 그려진 동물 그림이 서로 다르므로 방법만 알고 있다면 충분히 가능합니다!) 승현이를 도와주세요.
입력 형식
첫 번째 줄에 카드의 수를 나타내는 자연수 $n$이 주어집니다.
두 번째 줄에 $c_{1}, c_{2}, \cdots, c_{n}$이 공백을 사이에 두고 차례대로 주어집니다.
출력 형식
첫 번째 줄에 가능한 최대 합을 출력합니다.
부분문제
| 부분문제 | 점수 | $n$ | 추가 제약 사항 |
|---|---|---|---|
| 1 | 5 | $n = 1$ | - |
| 2 | 15 | $n = 2$ | - |
| 3 | 10 | $n =$ $2,222$ | - |
| 4 | 25 | $n \le$ $2,222$ | 모든 $1 \le i \le n$에 대하여 $c_{i} = i$ |
| 5 | 45 | $n \le$ $2,222$ | - |
예제
| 입력 1 | 출력 1 |
|---|---|
| 2 3 4 |
3 |
이 예제에서 가능한 경우는 한 가지 뿐입니다.
승현이는 3이 적힌 카드와 4가 적힌 카드를 뽑게 되고, 3이 적힌 카드를 갖고 나면 남은 카드가 한 장밖에 없으므로 답은 3이 됩니다.
| 입력 2 | 출력 2 |
|---|---|
| 3 1 3 5 |
4 |
이 예제에서 가능한 경우는 세 가지입니다.
- 승현이가 처음에 1이 적힌 카드와 3이 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
- 승현이가 처음에 1이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
- 승현이가 처음에 3이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 1이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 3+1=4가 됩니다.
따라서 답은 4가 됩니다.
| 입력 3 | 출력 3 |
|---|---|
| 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
190 |