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
#include <bits/stdc++.h>
#define dbg(x) #x << " = " << x << " "
#define dbgv(x)                        \
    #x << " = [";                      \
    for (auto i : x) cerr << " " << i; \
    cerr << " ] "
using namespace std;
using ld = long double;
constexpr int MAXN = 50'005, OFFSET = 50'000, INF = 4 * OFFSET;
constexpr ld TAK_MALO_ZE_MOGE_ZAPOMNIEC = 2e-11;
ld p[MAXN], dp[2 * MAXN][2];

// Mały paranoik.
bool jedynka(string s) {
    return s == "1" || s == "1.0" || s == "1.00" || s == "1.000"
    || s == "1.0000" || s == "1.00000" || s == "1.000000"
    || s == "1.0000000" || s == "1.00000000" || s == "1.000000000";
}

int main() {
    ios_base::sync_with_stdio(0);

    int n, t;
    cin >> n >> t;
    int darmowe = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        stringstream sz(s);
        sz >> p[i];

        if (jedynka(s)) darmowe++;
    }

    sort(p + 1, p + n + 1, [](ld a, ld b) { return a > b; });

    t -= darmowe;

    if (t <= 0) {
        cout << "1\n";
        return 0;
    }

    ld wynik = 0;

    dp[OFFSET][darmowe % 2] = 1;

    int zywe_l = OFFSET, zywe_r = OFFSET;
    for (int i = darmowe + 1; i <= n; i++) {
        int par = i % 2;

        int nowe_zywe_l = INF, nowe_zywe_r = -INF;
        for (int k = zywe_l - 1; k <= zywe_r + 1; k++) {
            dp[k][par] = dp[k - 1][1 - par] * p[i] + dp[k + 1][1 - par] * (1 - p[i]);
            if (dp[k][par] > TAK_MALO_ZE_MOGE_ZAPOMNIEC) {
                if (nowe_zywe_l == INF) nowe_zywe_l = k;
                nowe_zywe_r = k;
            }
        }

        for (int k = zywe_l; k <= zywe_r; k++) dp[k][1 - par] = 0;

        zywe_l = nowe_zywe_l;
        zywe_r = nowe_zywe_r;

        ld kandydat = 0;
        for (int k = max(t + OFFSET, nowe_zywe_l); k <= nowe_zywe_r; k++) {
            kandydat += dp[k][par];
        }

        if (kandydat > wynik) wynik = kandydat;
    }

    cout << fixed << setprecision(9) << wynik << "\n";
}