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
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000;
int N, T;
double dp[2*MAX]; // per MAX in each direction.
vector<double> p;
double mean = 0.0;
int shift = 0;
double ANS = 0.0;

int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);

	cin >> N >> T;
	double d;
	for(int i = 0; i < N; i++){
		cin >> d;
		p.push_back(d);
	}

	// now here is the algorithm: we calculate and update the 
	// array dp, which contains probability that our sum equals
	// a particular value. This array dp considers only values
	// at most MAX away from the mean. At any moment we keep:
	// shift = ceil(mean).
	// the initial values are like so:
	for(int i = 0; i < 2*MAX; i++){
		dp[i] = 0;
	}
	dp[MAX] = 1.0;

	sort(p.begin(), p.end());
	
	// now we append probabilities, from the largest to the smallest.
	for(int i = N - 1; i >= 0; i--){
		// update step first.

		// first update all values.
		int s = 1;
		if((s - MAX + shift + (N - 1 - i)) % 2 == 0){
			s++;
		}
		for(int j = s; j < 2*MAX - 1; j += 2){
			dp[j] = p[i] * dp[j - 1] + (1.0 - p[i]) * dp[j + 1];
		}

		// and zero out entries that ought to be zero.
		s = 0;
		if((s - MAX + shift + (N - 1 - i) + 1) % 2 == 0){
			s++;
		}
		for(int j = s; j < 2*MAX; j += 2){
			dp[j] = 0.0;
		}
		// borders are frankly irrelevant, and probably BEST left out as they are!

		// now onto the shift. First update the mean and the shift.
		mean += 2*p[i] - 1.0;
		int new_shift = ceil(mean);

		if(new_shift < shift){
			for(int i = 2*MAX - 1; i > 0; i--){
				dp[i] = dp[i - 1];
			}
			shift--;

		} else if(new_shift > shift){
			for(int i = 0; i < 2*MAX - 1; i++){
				dp[i] = dp[i + 1];
			}
			shift++;
		}

		// debug
		// for(int i = -10; i < 10; i++){
		// 	cout << dp[i + MAX] << ' ';
		// }
		// cout << "shift = " << shift << endl;

		// and finally, update the answer!
		double SUM = 0.0;
		for(int i = -MAX; i < MAX; i++){
			if(i + shift >= T){
				SUM += dp[i + MAX];
			}
		}
		// cout << "SUM = " << SUM << endl;
		
		ANS = max(ANS, SUM);
	}

	cout << setprecision(19) << fixed << ANS << endl;
}