1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iomanip>

using namespace std;

vector<float> readProb(int n){
    // wczytaj i posortuj malejaco prawdopodobienstwa zrobienia kolejnych zadan
    vector<float> P(n,0);
    float p;
    for (int i=0; i<n; i++){
        cin>>p;
        P[i]=p;
    }
    sort(P.begin(), P.end(), greater<float>());
    return P;
}

int prog_zdania(int i, int k){
    // # ile zadan trzeba rozwiazac dobrze sposrod i zeby zdobyc k punktow
    return k + (i-k)/2 + (i-k)%2;
    }

int main()
{
    int n,k;
    cin>>n>>k;
    vector<float> P = readProb(n);

    // zmienne operacyjne
    vector<float> tab(n+1,0), tab_prev(n+1,0);
    tab_prev[0]=1;
    vector<float> P_k(n+1,0);
    int progN = prog_zdania(n, k);

    // glowna petla
    for(int i=1; i<=n; i++){

        // spamietywanie - w i-tym kroku tab[j] zawiera prawdop. zrobienia dokladnie j zadan sposrod i
        int j0 = max(0, progN-(n-i));
        for(int j=j0; j<=i; j++){
            tab[j] = tab_prev[j] *(1-P[i-1]);
            if (j>0)
                tab[j] += tab_prev[j-1] *P[i-1];
        }

        // obliczenie prawdopodobienstwa zdania egzaminu przy i odpowiedziach
        if (i >=k){
            int prog = prog_zdania(i, k);
            P_k[i] = accumulate(tab.begin()+prog, tab.begin()+(i+1), 0.0);
        }

        // aktualizacja tab_prev
        tab_prev.swap(tab);
    }

    // odpowedz
    float ans = *max_element(P_k.begin(), P_k.end());
    cout<< fixed;
    cout<< setprecision(9);
    cout<< ans << endl;

    return 0;
}