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

using real = long double;


class Distribution
{
    const real THRESHOLD = 1.0e-14;

    int j_last, j_min, j_max;
    std::vector<real> data, prev; // zakres 0 do j_last, włącznie

public:
    Distribution(int j_last) : j_last(j_last), data(j_last+1, 0), prev(j_last+1, 0) {
	data[0] = 1;
	j_min = j_max = 0; // to jest zakres niezerowych elementów w data
    }

    void update(real p) {
	// prev should be all zeros outside of update
	std::swap(data, prev);
	for (int j=j_min; j<j_max; ++j) {
	    data[j] += (1-p) * prev[j];
	    data[j+1] += p * prev[j];
	}
	if (j_max < j_last) {
	    data[j_max] += (1-p) * prev[j_max];
	    data[j_max+1] += p * prev[j_max];
	    j_max++;
	} else {
	    data[j_max] += (1-p) * prev[j_max];
	}
	for (int j=j_min; j<=j_max; ++j) {
	    prev[j] = 0;
	}
	while (j_min < j_max && data[j_min] < THRESHOLD) {
	    data[j_min++] = 0;
	}
    }

    real sum(int jL, int jR) {
	jL = std::max(jL, j_min);
	jR = std::min(jR, j_max);
	real result = 0;
	for (int j=jL; j<=jR; ++j) {
	    result += data[j];
	}
	return result;
    }
};


// assume +1 for correct, 0 for wrong
int main() {
    int n, t;
    scanf("%d%d", &n, &t);

    const int max_j_for_success = (t+n+1)/2;

    std::vector<real> P(n);
    for (int i=0; i<n; ++i) {
	scanf("%Lf", &P[i]);
    }
    std::sort(P.rbegin(), P.rend());

    Distribution dist(max_j_for_success-1);
    for (int i=1; i<=t; ++i) {
	real p = P[i-1];
	dist.update(p);
    }
    real best_chance = 1.0 - dist.sum(0, t-1);

    int missed = 0;
    for (int i=t+1; i<=n; ++i) {
	int j_for_success = (t+i+1)/2;

	real p = P[i-1];
	dist.update(p);

	real next_chance = 1.0 - dist.sum(0, j_for_success-1);
	if (next_chance > best_chance) {
	    best_chance = next_chance;
	    missed = 0;
	} else if (++missed >= 4) {
	    break;
	}
    }

    printf("%.7Lf\n", best_chance);
}