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
67
68
69
70
71
72
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

template<class T> using ordered_set =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;

#define debug(x) cout << "[" <<  #x << " " << x << "] ";

#define ar array
#define ll long long
#define ld long double
#define sz(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

typedef vector<int> vi;
typedef pair<int,int> pi;

const int MAX_N = 5e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;

void solve() {
    int n,t;
    cin >> n >> t;
    vector<double> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    sort(p.rbegin(), p.rend());
    queue<pair<int,int>> point_to_eval;
    for (int i=t, j=0; i+2*j<=n; j++){
        point_to_eval.push({i+2*j,j});
    }

    // dp[i][j] = probability of fucking up i answers after choosing first j questions
    double ans = 0.0;
    vector<double> prev_dp(n+1,0.0);
    prev_dp[0] = 1.0;

    for (int i=1; i<=n; i++) {
        vector<double> dp(n+1,0.0);
        dp[0] = prev_dp[0] * p[i-1];
        for (int j=1; j<=i; j++) {
            dp[j] = prev_dp[j] * p[i-1] + prev_dp[j-1] * (1.0 - p[i-1]);
        }
        if (point_to_eval.front().first == i) {
            double cdf = 0.0;
            for (int j=0; j<=point_to_eval.front().second; j++){
                cdf += dp[j];
            }
            ans = max(ans,cdf);
            point_to_eval.pop();
        }
        prev_dp = dp;
    }

    cout << std::fixed << std::setprecision(20) << ans << "\n"; 
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t << ": ";
        solve();
    }
}