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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Marcin Knapik
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, b) for (int i = 0; i < b; ++i)
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

using K = long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define losuj(a, b) uniform_real_distribution<K>(a, b)(rng)
#define losuj_int(a, b) uniform_int_distribution<long long>(a, b)(rng)


const int N = 50001;

K dp[N][2];
K input[N];

void solve()
{
    int n, k;
    cin >> n >> k;
    dp[0][0] = 1;

    FOR (i, n)
    {
        cin >> input[i];
        // input[i] = losuj(0, 1);
    }

    sort(input, input + n);
    reverse(input, input + n);

    K ans = 0;

    int last_asked_height = k;
    int which_i = k - 1;

    while (which_i + 2 < n)
    {
        which_i += 2;
        last_asked_height++;
    }

    int on_which_i_to_start_incline = which_i - last_asked_height;
    int incline = 0;

    for (int i = 0; i < n; ++i)
    {
        int _0 = i % 2;
        int _1 = _0 ^ 1;
        K p = input[i];

        dp[0][_1] = 1;
        int max_height = min(i + 1, last_asked_height);
        int min_height = 1;
        if (i >= on_which_i_to_start_incline)
        {
            min_height = max(incline, 1);
        }

        for (int j = min_height; j <= max_height; ++j)
        {
            dp[j][_1] = dp[j][_0] * (1 - p) + dp[j - 1][_0] * p;
        }
        
        if (i + 1 >= k)
        {
            ans = max(ans, dp[i + 1 - (i + 1 - k) / 2][_1]);
        }
        if (i >= on_which_i_to_start_incline)
        {
            incline++;
        }
    }

    cout << setprecision(15) << fixed << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t = 1;
    // cin >> t;

    FOR(test, t)
    {
        solve();
    }
    return 0;
}