시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB134440.000%

문제

아름이는 컴퓨터 게임을 하고 있다. 이 게임은 총 n개의 레벨로 이루어져 있으며, 1번부터 n번까지 번호가 매겨져 있다.

레벨은 총 k개의 그룹으로 나누어져 있으며, 그룹은 연속된 레벨로 이루어져 있다.

게임은 다음 과정을 반복한다.

  1. 모든 구역을 정복했으면 게임은 끝난다. 그 외의 경우에는 깨지 못한 레벨이 적어도 하나 있는 첫 번째 그룹을 시스템이 찾는다. 이 그룹을 X라고 한다.
  2. 시스템은 코인을 담을 수 있는 가방 하나를 생성한다. 각 코인은 레벨 하나를 나타내며, 여러 개의 코인이 같은 레벨을 나타낼 수도 있다.
    • 그룹 X에 있는 레벨 i를 이미 깼다면, 시스템은 ti개의 코인을 가방에 추가한다. (이때 추가하는 코인은 레벨 i를 나타낸다)
    • j를 그룹 X에서 깨지못한 첫 번째 스테이지라고 했을 때, 시스템은 tj개의 코인을 가방에 추가한다. (이때 추가하는 코인은 레벨 j를 나타낸다)
  3. 시스템은 랜덤하게 가방에서 코인을 하나 선택하고, 아름이에게 코인이 나타내는 레벨을 알려준다. 아름이는 그 레벨을 한 시간 동안 깬다. 이미 그 레벨을 깼다고 해도 깨며, 항상 클리어할 수 있다.

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까지 허용한다.

예제 입력 1

4 2
100 3 5 7

예제 출력 1

5.7428571429

예제 입력 2

6 2
1 2 4 8 16 32

예제 출력 2

8.5000000000

힌트

첫 번째 예제의 경우에 첫 번째 레벨과 나머지로 나누는 것이 최적의 방법이다.

두 번째 예제의 경우에는 세 레벨 씩 나누는 것이 최적의 방법이다.

출처