소 대학

농부 존은 소들을 위한 새 대학을 열 계획이다!

이 대학에 다닐 가능성이 있는 소가 \(N\)마리(\(1 \le N \le 10^5\)) 있다. 각 소는 최대 \(c_i\) (\(1 \le c_i \le 10^6\))의 등록금까지 낼 의향이 있다. 농부 존은 모든 소가 입학하기 위해 내야 하는 등록금을 정할 수 있다. 이 등록금이 어떤 소가 낼 의향이 있는 최대 금액보다 크면, 그 소는 대학에 다니지 않는다. 농부 존은 교직원들에게 정당한 임금을 주기 위해 가능한 한 많은 돈을 벌고 싶다. 그가 벌 수 있는 최대 금액과 얼마의 등록금을 매겨야 하는지 구하시오.

출제: Freddie Tang

배점

• 테스트 케이스 2부터 4까지는 \(c_i \le 1{,}000\)이다.
• 테스트 케이스 5부터 8까지는 \(N \le 5{,}000\)이다.
• 테스트 케이스 9부터 12까지는 추가 제약이 없다.

출제: Freddie Tang

첫째 줄에 \(N\)이 주어진다. 둘째 줄에 \(N\)개의 정수 \(c_1, c_2, \dots, c_N\)이 주어지며, \(c_i\)는 소 \(i\)가 낼 의향이 있는 최대 등록금이다.

농부 존이 벌 수 있는 최대 금액과 그가 매겨야 할 최적의 등록금을 출력한다. 답이 여러 개인 경우, 최적 등록금이 가장 작은 답을 출력한다.

이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: Java의 "long", C/C++의 "long long")이 필요할 수 있음에 유의한다.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > December > Bronze