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
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7;
int ile[LIM];
ld T[LIM], wynik[LIM];
vector<ld>tr[4*LIM];


using cd = complex<ld>;
const ld PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
    int n = a.size();

    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1)
            j ^= bit;
        j ^= bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    for (int len = 2; len <= n; len <<= 1) {
        ld ang = 2 * PI / len * (invert ? -1 : 1);
        cd wlen(cos(ang), sin(ang));
        for (int i = 0; i < n; i += len) {
            cd w(1);
            for (int j = 0; j < len / 2; j++) {
                cd u = a[i+j], v = a[i+j+len/2] * w;
                a[i+j] = u + v;
                a[i+j+len/2] = u - v;
                w *= wlen;
            }
        }
    }

    if (invert) {
        for (cd & x : a)
            x /= n;
    }
}

vector<ld>mnoz(vector<ld>A, vector<ld>B) {
	int n=1;
	while(n<A.size()+B.size()) n*=2;
	vector<cd>fA(n), fB(n);
	rep(i, A.size()) fA[i]=A[i];
	rep(i, B.size()) fB[i]=B[i];
	fft(fA, false);
	fft(fB, false);
	rep(i, n) fA[i]*=fB[i];
	fft(fA, true);
	vector<ld>C(A.size()+B.size()-1);
	rep(i, C.size()) C[i]=fA[i].real();
	return C;
}

void licztr(int v, int l, int r) {
	if(l==r) {
		tr[v]={(ld)1-T[l], T[l]};
		return;
	}
	int mid=(l+r)/2;
	licztr(2*v, l, mid);
	licztr(2*v+1, mid+1, r);
	tr[v]=mnoz(tr[2*v], tr[2*v+1]);
}
void solve(int v, int l, int r, vector<ld>&P) {
	int dl=r-l+1, prz=max(ile[l]-dl, 0);
	if(l==r) {
		if(ile[l]-prz>=0 && ile[l]-prz<P.size()) wynik[l]+=P[ile[l]-prz]*((ld)1-T[l]);
		if(ile[l]-1-prz>=0 && ile[l]-1-prz<P.size()) wynik[l]+=P[ile[l]-1-prz]*T[l];
		return;
	}
	int mid=(l+r)/2;
	// [l, mid] chce dostac ile[l]-d/2, ile[mid]
	vector<ld>A;
	rep(i, P.size()) if(ile[l]-(mid-l+1)<=prz+i && prz+i<=ile[mid]) A.pb(P[i]);
	solve(2*v, l, mid, A);
	vector<ld>B=mnoz(P, tr[2*v]);
	// [mid+1, r] chce dostac ile[mid+1]-d/2, ile[r]
	vector<ld>C;
	rep(i, B.size()) if(ile[mid+1]-(r-mid)<=prz+i && prz+i<=ile[r]) C.pb(B[i]);
	solve(2*v+1, mid+1, r, C);
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, t;
	cin >> n >> t;
	for(int i=1; i<=n; ++i) {
		if(i>=t) ile[i-1]=(i+t+1)/2;
		else ile[i-1]=i;
		ile[i-1]=i-ile[i-1];
	}
	rep(i, n) {
		cin >> T[i];
		T[i]=(ld)1-T[i];
	}
	sort(T, T+n);
	licztr(1, 0, n-1);
	vector<ld>P(ile[n-1]+1, 1);
	solve(1, 0, n-1, P);
	ld ans=0;
	rep(i, n) if(i+1>=t) ans=max(ans, wynik[i]);
	cout << fixed << setprecision(7) << ans << '\n';
}