시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 190 48 43 33.858%

문제

이제 조금밖에 남지 않은 겨울 기분을 만끽하고 싶은 수현이는 지금부터라도 크리스마스 트리를 장식하려고 한다.

크리스마스 트리는 전구 스트립으로 두른다. 전구 스트립에는 전구 $N$개가 일(一)자로 설치되어 있고, 왼쪽에 전원을 넣는다. 특이하게도 이 전구 스트립은 전구 하나가 고장 나면 고장 난 전구를 시작으로 오른쪽에 설치되어 있는 모든 전구에 불이 들어오지 않게 된다.

수현이는 반짝반짝한 걸 좋아한다. 따라서 전구 스트립을 최대 $K$개의 토막으로 자르고, 왼쪽에 전원을 각각 다시 넣어서 트리를 장식할 것이다. 이렇게 해서 불이 들어온 전구의 개수의 기댓값이 최대가 되게 하고 싶다. 각각의 전구가 고장 날 확률이 주어질 때 불이 들어온 전구의 개수의 기댓값의 최댓값을 계산하라.

입력

다음과 같이 입력이 주어진다.

$N\ K$
$p_1\ p_2\,\dots\ p_N$
  • $N$은 전구 스트립의 길이이다. ($1 \leq N \leq 2\,500$)
  • $1 \leq K \leq \min \left\{ N, 10 \right\}$
  • $p_i$는 전구가 고장 날 확률이며, 소수점 아래 두 자리까지 주어진다. 왼쪽 전구에서 오른쪽 전구의 순서로 주어진다. ($0 \leq p_i \leq 1$)
  • $N$과 $K$는 정수다.

출력

불이 들어온 전구의 개수의 기댓값의 최댓값을 출력한다.

출력한 값과 정답과의 절대 오차 또는 상대 오차가 $10^{-6}$ 이하여야 한다.

예제 입력 1

5 1
0.50 0.50 0.50 0.50 0.50

예제 출력 1

0.96875

예제 입력 2

5 2
0.50 0.50 0.50 0.50 0.50

예제 출력 2

1.625

예제 입력 3

5 2
0.10 0.20 0.30 0.40 0.50

예제 출력 3

3.024