Twinkle Twinkle

Time limit2sMemory limit1024 MB

Summary

Cut a strip of N bulbs into at most K pieces, each powered from its left end; a bulb lights only if it and all bulbs left of it within its piece survive. Maximize the expected number of lit bulbs.

Level: Medium7 of 10
Topics: Dynamic programming, Probability, Prefix sum, Divide and conquer
Solved: No attempts yet

Problem

With only a little of the winter mood left, Suhyeon decides to decorate a Christmas tree now.

The Christmas tree is wrapped with a strip of lights. The strip holds $N$ bulbs in a straight line, and power is fed in at the left end. Unusually, when one bulb fails, every bulb to its right, starting with the failed bulb, goes dark.

Suhyeon likes things that twinkle. So she will cut the strip into at most $K$ pieces and feed power in at the left end of each piece to decorate the tree. She wants the expected number of lit bulbs to be as large as possible. Given the failure probability of each bulb, compute the maximum possible expected number of lit bulbs.

Input

The input is given as follows.

$N\ K$

$p_1\ p_2\ \dots\ p_N$

Output

Print the maximum possible expected number of lit bulbs.

The absolute or relative error between your output and the correct answer must be at most $10^{-6}$ .

Constraints

$N$ is the length of the light strip. ( $1 \leq N \leq 2\,500$ )
$1 \leq K \leq \min \left\{ N, 10 \right\}$
$p_i$ is the failure probability of a bulb, given to two decimal places, ordered from the leftmost bulb to the rightmost. ( $0 \leq p_i \leq 1$ )
$N$ and $K$ are integers.

Examples3

Example 1
Input
```
5 1
0.50 0.50 0.50 0.50 0.50
```
Expected output
```
0.96875
```
Example 2
Input
```
5 2
0.50 0.50 0.50 0.50 0.50
```
Expected output
```
1.625
```
Example 3
Input
```
5 2
0.10 0.20 0.30 0.40 0.50
```
Expected output
```
3.024
```