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
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>
using namespace std;
#define V vector
#define Q queue
#define PQ priority_queue
#define ST stack
#define UMAP unordered_map
typedef long long LL;
typedef double LD;
typedef pair<int, int> PII;
typedef V<int> VI;
typedef V<V<int>> VVI;

constexpr int MAXNT = 50'007;
constexpr int MAXSIZE = MAXNT+MAXNT;
LD prob[MAXSIZE];
LD prob2[MAXSIZE];
LD vals[MAXNT];

inline bool comp(LD a, LD b) {
    return a > b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    for (int i = 0; i < MAXSIZE; ++i)
        prob[i] = 0;

    prob[MAXNT] = 1;

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> vals[i];

    sort(vals, vals+n, comp);

    LD best = 0;
    int l = MAXNT;
    int r = MAXNT;
    int z = k&1;
    if (z) {
        LD sum = 0;
        --l;
        ++r;
        int maxBord = MAXNT-(k>>1)-10;
        if ((l&1) && !(maxBord&1)) {
            --maxBord;
        } else if (!(l&1) && (maxBord&1)) {
            --maxBord;
        }
        for (int j = max(l, maxBord); j < r; j += 2)
            prob2[j] = prob[j+1]*(1-vals[0]);
        prob2[r] = 0;
        for (int j = max(l+2, maxBord); j <= r; j += 2)
            prob2[j] += prob[j-1]*vals[0];
        for (int j = max(l, maxBord); j <= r; j += 2) {
            prob[j] = prob2[j];
            if (prob[j] < 1e-12)
                prob[j] = 0;
        }
        while (prob[l] == 0)
            l += 2;
        while (prob[r] == 0)
            r -= 2;
        for (int j = r; j >= MAXNT + k; j -= 2)
            sum += prob[j];
        best = max(best, sum);
    }

    for (int i = z; i+1 < n; i += 2) {
        LD sum = 0;
        l -= 2;
        r += 2;
        int maxBord = MAXNT-(k>>1)-10;
        if ((l&1) && !(maxBord&1)) {
            --maxBord;
        } else if (!(l&1) && (maxBord&1)) {
            --maxBord;
        }
        pair<LD,pair<LD,LD>> poly;
        poly.first = ((1-vals[i])*(1-vals[i+1]));
        poly.second.first = ((vals[i]*(1-vals[i+1]))+(vals[i+1]*(1-vals[i])));
        poly.second.second = (vals[i]*vals[i+1]);
        prob2[r] = 0;
        for (int j = max(l, maxBord); j < r; j += 2)
            prob2[j] = prob[j+2]*poly.first;
        for (int j = max(l+2, maxBord); j < r; j += 2)
            prob2[j] += prob[j]*poly.second.first;
        for (int j = max(l+4, maxBord); j <= r; j += 2)
            prob2[j] += prob[j-2]*poly.second.second;
        for (int j = max(l, maxBord); j <= r; j += 2)
            prob[j] = prob2[j];
        for (int j = r; j >= MAXNT + k; j -= 2)
            sum += prob[j];
        best = max(best, sum);
    }

    cout << fixed << setprecision(9);
    cout << best << '\n';

    return 0;
}