시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB2631028638.053%

문제

인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다.

인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (+ 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라.

하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶다.

N개의 인형을 모두 사용하여, 마트료시카들을 판매한다고 할 때, 하령이가 올릴 수 있는 최대 수익은 얼마인가?

입력

첫째 줄에 인형의 개수 N이 주어진다. (1 ≤ N ≤ 2 × 105)

둘째 줄에 하령이가 가지고 있는 인형들의 크기를 나타내는 N개의 정수 Xi가 공백으로 구분되어 주어진다. (1 ≤ Xi ≤ 105)

출력

하령이가 올릴 수 있는 최대 수익을 출력하시오.

정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.

예제 입력 1

6
1 3 4 5 7 8

예제 출력 1

32

예제 입력 2

7
5 3 4 10 4 8 9

예제 출력 2

49

세 개의 마트료시카 (3, 4, 5), (4). (8, 9, 10)로 구성하는 것이 최선이다. 이때, 각 마트료시카의 가격은 15, 4, 30이다.

출처

University > 인천대학교 > INU 코드페스티벌 2021 E번