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
#include <iostream>
#include <vector>
#include <algorithm>

int const MAX_N = 50010;                                 /// ZMIEŃ

double prob[2][2 * MAX_N + 1]; //PROBABILITY FROM P(S=-n) to P(S=N)
int main()
{
	std::vector<double> prob_q = std::vector<double>();
	int n, t;
	std::cin >> n >> t;
	for (int i = 0; i < n; i++) {
		double a;
		std::cin >> a;
		prob_q.push_back(a);
	}

	std::sort(begin(prob_q), end(prob_q), std::greater<double>());


	for (int i = 0; i < 2 * n + 1; i++) {
		prob[0][i] = 0.0;
		prob[1][i] = 0.0;
	}
	prob[0][n + 0] = 1.0;
	double max_pass_prob = 0.0;
	double pass_prob = 0.0;
	int offset_neg = 0;
	int offset_pos = 0;
	for (int i = 0; i < n; i++) {
		pass_prob += prob[i % 2][n + t - 1] * prob_q[i] - prob[i % 2][n + t] * (1 - prob_q[i]);
		max_pass_prob = std::max(pass_prob, max_pass_prob);

		for (int k = 2 * offset_neg; k <= 2*i +3 - 2*offset_pos; k += 2) {
			prob[(i + 1) % 2][n - i - 1 + k] = prob[i % 2][n - i - 1 + k - 1] * prob_q[i] + prob[i % 2][n - i - 1 + k + 1] * (1 - prob_q[i]);
		}
		if (prob[(i + 1) % 2][n - i - 1 + 2 * offset_neg] < 1e-15) offset_neg++;
		if (prob[(i + 1) % 2][n + i + 1 - 2*offset_pos] < 1e-15) offset_pos++;

		//std::cout << pass_prob << "\n";
	}
	std::printf("%.7f", max_pass_prob);
	//std::cout << max_pass_prob;
}