시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 13 | 4 | 4 | 40.000% |
아름이는 컴퓨터 게임을 하고 있다. 이 게임은 총 n개의 레벨로 이루어져 있으며, 1번부터 n번까지 번호가 매겨져 있다.
레벨은 총 k개의 그룹으로 나누어져 있으며, 그룹은 연속된 레벨로 이루어져 있다.
게임은 다음 과정을 반복한다.
n과 k, 그리고 t1, t2, ..., tn이 주어졌을 때, 적절히 레벨을 그룹으로 나눈다. 모든 레벨을 하나의 그룹에 속해야 하며, 모든 그룹은 연속된 레벨을 나타내야 한다. 게임을 모두 마치는데 필요한 시간의 최솟값의 기댓값을 구하는 프로그램을 작성하시오.
첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 200,000, 1 ≤ k ≤ min(50, n))
둘째 줄에는 t1, t2, ..., tn (1 ≤ ti ≤ 100,000)이 주어진다.
레벨의 최적의 방법으로 그룹을 나눴을 때 게임을 클리어하는데 필요한 시간의 최솟값의 기댓값을 출력한다. 절대/상대 오차는 10-4까지 허용한다.
4 2 100 3 5 7
5.7428571429
6 2 1 2 4 8 16 32
8.5000000000
첫 번째 예제의 경우에 첫 번째 레벨과 나머지로 나누는 것이 최적의 방법이다.
두 번째 예제의 경우에는 세 레벨 씩 나누는 것이 최적의 방법이다.