시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 96 | 25 | 20 | 29.851% |
N개의 부서를 하나의 부서로 합치고자 한다. 이 부서들에 1에서 N까지의 번호를 붙이고, 부서 i의 크기를 Si라고 하도록 하자. 한 번에 많은 부서를 합치면 혼란이 커질 것이라고 예상되었기 때문에, 두 개의 부서를 하나로 합치는 것을 N - 1번 반복하여 통합된 하나의 부서를 만들기로 하였다. 반복하는 과정은 아래와 같다.
두 부서를 합치는 데에는 비용이 발생한다. 이때 합치는 방법에 따라 드는 비용이 다르지만 우리는 비용이 Sa × Sb인 방법을 알고 있고, 이를 사용할 것이다. 이때 드는 총비용의 최솟값과, 최소한의 비용이 들게 하는 서로 다른 과정의 가짓수를 구해보자. 두 과정이 서로 다르다는 것은, 기록된 쌍들을 순서대로 하나씩 비교했을 때 한 쌍이라도 다르다는 것이다.
첫 번째 줄에 부서의 수를 의미하는 자연수 N (1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄에는 각 부서의 크기를 의미하는 N개의 자연수 S1, S2, ..., SN이 공백으로 구분되어 주어진다. 이 수들은 1 이상 100 이하이다.
첫 번째 줄에는 총비용의 최솟값을 출력한다.
두 번째 줄에는 최소한의 비용이 들게 하는 서로 다른 과정의 가짓수를 1,000,000,007로 나눈 나머지를 출력한다.
2 2 3
6 2
(1,2)와 (2,1)은 서로 다른 경우이다.
Contest > kriiicon > 제2회 kriiICPC U번