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
// Homura Akemi a.k.a. Starrykiller (/user/235125)
// I love Madoka Kaname forever! 
#include <bits/stdc++.h>

using namespace std;

auto range(auto l, auto r) { return views::iota(l,r); }
auto rev=views::reverse;

_GLIBCXX_ALWAYS_INLINE void chmax(auto &a, auto b) { a=max(a,b); }
_GLIBCXX_ALWAYS_INLINE void chmin(auto &a, auto b) { a=min(a,b); }

// using db=double;
// auto pi=acos(-1);

using db=long double;
auto pi=acosl(-1);
using cp=complex<db>;
constexpr cp I(0,1);
constexpr int MAXN=262144+10;

void fft(cp f[], int n, int sgn=1) {
    int bit=__lg(n);
    // 位逆序置换
    static int rev[MAXN];
    for (int i=0; i<n; ++i) {
        rev[i]=(rev[i>>1]>>1) | ((i&1))<<(bit-1);
        if (i<rev[i]) swap(f[i], f[rev[i]]);
    }

    for (int l=1; l<n; l<<=1) { // 区间长度
        cp step=exp(sgn*pi/l*I);
        for (int i=0; i<n; i+=l<<1) {
            cp cur(1, 0);
            for (int k=i; k<i+l; ++k) {
                cp g=f[k], h=f[k+l]*cur;
                f[k]=g+h, f[k+l]=g-h;
                cur*=step;
            }
        }
    }
}

using poly=vector<db>;
poly conv(poly f, poly g) {
    int n=size(f)+size(g)-1;
    int N=1<<__lg(n+1)+1;
    f.resize(N); g.resize(N);
    vector<cp> F(N);
    for (int i=0; i<N; ++i) F[i]=cp(f[i],g[i]);
    fft(data(F),N);
    for (int i=0; i<N; ++i) F[i]*=F[i];
    fft(data(F),N,-1);
    poly h(n);
    for (int i=0; i<n; ++i) h[i]=F[i].imag()/(N*2);
    return h;
}

poly f[MAXN];
db p[MAXN]; int n, t;

#define ls(p) (p<<1)
#define rs(p) (p<<1|1)

void init(int l, int r, int p=1) {
    if (l==r) {
        f[p]={1,::p[l]};
        return;
    }
    int mid=(l+r)>>1;
    init(l,mid,ls(p));
    init(mid+1,r,rs(p));
    f[p]=conv(f[ls(p)],f[rs(p)]);
    // cerr<<l<<" "<<r<<": ";
    // for (auto i: f[p]) cerr<<i<<' '; cerr<<'\n';
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>n>>t;
    for (int i=1; i<=n; ++i) cin>>p[i];
    sort(p+1,p+1+n,greater());
    int N=1<<__lg(n+1)+1;
    vector<cp> f(n,1); f.resize(N);
    fft(data(f),N);
    db ans=0;
    for (int i=1; i<=n; ++i) {
        vector<cp> tmp(N);
        tmp[0]=1-p[i]; tmp[1]=p[i];
        fft(data(tmp),N);
        for (int k=0; k<N; ++k) {
            f[k]*=tmp[k];
            tmp[k]=f[k];
        }
        fft(data(tmp),N,-1);
        auto cur=1-tmp[(i+t+1)/2-1].real()/N;
        chmax(ans,cur);
        // cerr<<i<<" -> "<<fixed<<setprecision(20)<<cur<<'\n';
    }
    cout<<fixed<<setprecision(9)<<ans<<'\n';
    // init(1,n);
    // for (auto i: f[1]) cout<<fixed<<setprecision(20)<<i<<'\n';
}