Egzamin

시간 제한3초메모리 제한2048 MB

요약

각 문제의 정답 확률이 독립일 때, t점 이상을 받을 확률이 최대가 되도록 답할 문제 집합을 고른다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 정렬, 그리디, 확률
정답자: 아직 제출이 없습니다

문제

Marysia podchodzi do egzaminu składającego się z $n$ pytań. Odpowiedź na każde pytanie oceniana jest następująco:

$1$ punkt za poprawną odpowiedź,
$0$ punktów za brak odpowiedzi,
$-1$ punkt za błędną odpowiedź.

Żeby zdać egzamin, trzeba zdobyć co najmniej $t$ punktów.

Dla każdego pytania Marysia ustaliła potencjalną odpowiedź, ale nie zawsze jest pewna, czy jest ona poprawna. Dokładniej, dla $i$ -tego pytania wie, że odpowiedź jest poprawna z prawdopodobieństwem $p\_i$ . Poprawność odpowiedzi dla różnych pytań to zdarzenia niezależne.

Marysia musi wybrać, na które pytania udzielić odpowiedzi, a które zostawić bez odpowiedzi, żeby zmaksymalizować prawdopodobieństwo zdania egzaminu.

입력

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite $n$ , $t$ ( $1 ≤ t ≤ n ≤ 50\\, 000$ ): liczba pytań i wymagana minimalna liczba punktów.

W kolejnych $n$ wierszach znajdują się prawdopodobieństwa poprawności odpowiedzi: $i$ -ty z tych wierszy zawiera liczbę rzeczywistą $p\_i$ ( $0 ≤ p\_i ≤ 1$ ), która ma co najwyżej $9$ cyfr po kropce dziesiętnej.

출력

W jedynym wierszu wyjścia powinna znaleźć się jedna liczba rzeczywista: prawdopodobieństwo, że Marysia zda egzamin, jeśli optymalnie wybierze, na które pytania udzielić odpowiedzi. Liczba musi być wypisana w postaci dziesiętnej (nie wykładniczej) z co najwyżej $20$ miejscami po przecinku.

Maksymalny dopuszczalny błąd bezwzględny to $10^{-6}$ .

힌트

Wyjaśnienie przykładów: W pierwszym przykładzie optymalną strategią jest odpowiedzieć na pierwsze $4$ pytania, a ostatnie zostawić bez odpowiedzi. W ten sposób nawet przy jednej błędnej odpowiedzi Marysia uzyska $2$ punkty.

W drugim przykładzie optymalną strategią jest odpowiedzieć na pierwsze, trzecie i czwarte pytanie. Marysia uzyska $3$ punkty, jeśli wszystkie te odpowiedzi będą poprawne. Ponieważ te zdarzenia są niezależne, prawdopodobieństwo wynosi $0,3 \cdot 0,2 \cdot 0,15 = 0,009$ .

W ostatnim przykładzie prawdopodobieństwo sukcesu to $10^{-18}$ , możemy je zaokrąglić do $0$ .

예제3

예제 1
입력
```
5 2
0.77
0.85
0.75
0.98
0.6
```
예상 출력
```
0.8798125
```
예제 2
입력
```
5 3
0.3
0.01
0.2
0.15
0
```
예상 출력
```
0.009
```
예제 3
입력
```
3 3
0.000001
0.000001
0.000001
```
예상 출력
```
0
```