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
#include<bits/stdc++.h>
#define LL long long
#define LLL __int128
#define uint unsigned
#define ldb long double
#define uLL unsigned long long
using namespace std;
typedef complex<ldb> comp;
typedef vector<ldb> poly;
namespace Polynomial{
const int N=1e6+5;
const ldb pi=acosl(-1.0);
int lim,len,r[N];
comp a[N],b[N];
void getr(int n){
    for(lim=1,len=0;lim<=n;lim<<=1,++len);
    for(int i=0;i<lim;++i)r[i]=(r[i>>1]>>1)|((i&1)<<(len-1));
}
void FFT(comp *A,int n,int op){
	for(int i=0;i<n;++i)
		if(i<r[i])swap(A[i],A[r[i]]);
	for(int i=1;i<n;i<<=1){
		comp w0=comp(cos(pi/i),op*sin(pi/i));
		int rr=i<<1;
		for(int j=0;j<n;j+=rr){
			comp w=comp(1,0);
			for(int k=0;k<i;++k,w*=w0){
				comp x=A[j+k];
				comp y=A[i+j+k]*w;
				A[j+k]=x+y,A[i+j+k]=x-y;
			}
		}
	}
    if(op!=1)for(int i=0;i<n;++i)a[i]/=n;
}
inline poly Mul(poly A,poly B){
	getr(A.size()+B.size()-2);
	for(int i=0;i<A.size();++i)a[i]=A[i];
	for(int i=A.size();i<lim;++i)a[i]=0;
	for(int i=0;i<B.size();++i)b[i]=B[i];
	for(int i=B.size();i<lim;++i)b[i]=0;
	FFT(a,lim,1);FFT(b,lim,1);
	for(int i=0;i<lim;++i)a[i]*=b[i];
	FFT(a,lim,-1);
	A.resize(A.size()+B.size()-1);
	for(int i=0;i<A.size();++i)A[i]=a[i].real();
	return A;
}
}
const int N=5e4+5;
int n,q;
poly Q[N];
ldb ans,a[N],f[N];
inline ldb calc(int k){
	if(f[k]>=0)return f[k];
	poly P({1});
	for(int i=k;i;i-=i&-i)P=Polynomial::Mul(P,Q[i]);
	f[k]=0;
	for(int i=0;i<P.size();++i)
		if(i-(k-i)>=q)f[k]+=P[i];
	ans=max(ans,f[k]);
	return f[k];
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>n>>q;
	for(int i=1;i<=n;++i)cin>>a[i],f[i]=-1;
	sort(a+1,a+n+1,greater<>());
	for(int i=1;i<=n;++i)Q[i]=poly({1});
	for(int i=1;i<=n;++i){
		Q[i]=Polynomial::Mul(Q[i],poly({1-a[i],a[i]}));
		int j=i+(i&-i);
		if(j<=n)Q[j]=Polynomial::Mul(Q[i],Q[j]);
	}
	for(int l=1,r=n/2;l<r;){
		const int mid=(l+r)>>1;
		if(calc(mid*2)<=calc((mid+1)*2))l=mid+1;
		else r=mid;
	}
	for(int l=1,r=(n+1)/2;l<r;){
		const int mid=(l+r)>>1;
		if(calc(mid*2-1)<=calc((mid+1)*2-1))l=mid+1;
		else r=mid;
	}
	cout<<fixed<<setprecision(10)<<ans<<'\n';
    return 0;
}