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
116
117
118
119
120
121
122
#include<bits/stdc++.h>
#define st first
#define nd second
#define all(x) x.begin(), x.end()
#define BOOST cin.tie(NULL); ios_base::sync_with_stdio(false);



// #define int ll
typedef long long ll;
typedef double ld;

using namespace std;
template <typename T> struct tag:reference_wrapper <T>{ using reference_wrapper <T>::reference_wrapper; };
template <typename T1, typename T2> static inline tag <ostream> operator<<(tag <ostream> os, pair<T1, T2> const& p){ return os.get()<<"{"<<p.first<<", "<<p.second<<"}", os;}
template <typename Other> static inline tag <ostream> operator<<(tag <ostream> os, Other const& o){ os.get()<<o; return os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, vector <T> const& v){ os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }
template <typename T> static inline tag <ostream> operator <<(tag <ostream> os, set <T> const& s){ vector <T> v; for (auto i: s) v.push_back(i); os.get()<<"["; for (int i=0; i<v.size(); i++) if (i!=v.size()-1) os.get()<<v[i]<<", "; else os.get()<<v[i]; return os.get()<<"]", os; }


// ------------  poczatek kodu przekopiowanego z biblioteczki  ------------ //
// Przekopiowane z Omogen Heap https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/FastFourierTransform.h
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;


typedef complex<ld> C;
typedef vector<ld> vd;
void fft(vector<C>& a) {
	int n = sz(a), L = 31 - __builtin_clz(n);
	static vector<complex<long double>> R(2, 1);
	static vector<C> rt(2, 1);  // (^ 10% faster if double)
	for (static int k = 2; k < n; k *= 2) {
		R.resize(n); rt.resize(n);
		auto x = polar(1.0L, acos(-1.0L) / k);
		rep(i,k,2*k) rt[i] = R[i] = i&1 ? R[i/2] * x : R[i/2];
	}
	vi rev(n);
	rep(i,0,n) rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
	rep(i,0,n) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int k = 1; k < n; k *= 2)
		for (int i = 0; i < n; i += 2 * k) rep(j,0,k) {
			// C z = rt[j+k] * a[i+j+k]; // (25% faster if hand-rolled)  /// include-line
			auto x = (ld *)&rt[j+k], y = (ld *)&a[i+j+k];        /// exclude-line
			C z(x[0]*y[0] - x[1]*y[1], x[0]*y[1] + x[1]*y[0]);           /// exclude-line
			a[i + j + k] = a[i + j] - z;
			a[i + j] += z;
		}
}
vd conv(const vd& a, const vd& b) {
	if (a.empty() || b.empty()) return {};
	vd res(sz(a) + sz(b) - 1);
	int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
	vector<C> in(n), out(n);
	copy(all(a), begin(in));
	rep(i,0,sz(b)) in[i].imag(b[i]);
	fft(in);
	for (C& x : in) x *= x;
	rep(i,0,n) out[i] = in[-i & (n - 1)] - conj(in[i]);
	fft(out);
	rep(i,0,sz(res)) res[i] = imag(out[i]) / (4 * n);
	return res;
}
// ------------  koniec kodu przekopiowanego z biblioteczki  ------------ //


int n, t;
vector<ld> quest;
vector<ld> ans;

vector<ld> prob[2];
int shift;

ld find_probability(int k){
    int curr = (k&1);
    // cout << "K:  " << k << "\n";
    for(int i = shift + t - (n - k - 1) - 3; i <= shift + k + 1; i++){
        prob[curr][i] = prob[(curr^1)][i - 1] * quest[k] + prob[(curr^1)][i + 1] * (1.0 - quest[k]);
    }
    ld answer = 0.0;
    for(int i = shift + t; i <= shift + k + 1; i++){
        if(prob[curr][i] > 0) answer += prob[curr][i];
    }
    return answer;
}

int32_t main(){
    BOOST;
    cout << fixed << setprecision(7);
    
    cin >> n >> t;
    prob[0].assign(2 * n + 20, 0.0);
    prob[1].assign(2 * n + 20, 0.0);
    shift = n + 10;

    quest.resize(n);
    ans.resize(n + 1, 0.0);
    for(int i = 0; i < n; i++){
        cin >> quest[i];
    }
    sort(all(quest), greater<ld>());

    // cout << "ok0" << endl;
    

    ld answer = 0.0;
    prob[1][shift] = 1.0;
    // cout << "ok1" << endl;
    for(int i = 0; i < n; i++){
        ans[i] = find_probability(i);
        if(ans[i] == 0.0) continue;
        if(ans[i] < answer) n = min(n, i + 3);
        answer = max(answer, ans[i]);
    }

    // cout << ans << "\n";

    cout << fixed << setprecision(7) << answer << "\n";
    return 0;
}