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

int n, t;
double prob_list[50004];
double res;

std::vector<double> poly[2];

void read_input();
void sort_probs();
void solve();
void print_result();

int main() {
    read_input();
    sort_probs();
    solve();
    print_result();
}

void read_input() {
    std::cin >> n >> t;
    for (int i = 0; i < n; ++i) {
        std::cin >> prob_list[i];
    }
}

void sort_probs() {
    std::sort(prob_list, prob_list + n, std::greater<double>());
}

void solve() {
    poly[0].push_back(1 - prob_list[0]);
    poly[0].push_back(prob_list[0]);

    if (t == 1) {
        res = prob_list[1];
    }

    int max_score = 1;
    for (int i = 0; i < n - 1; ++i) {
        double curr_prob = 0;
        int curr = i % 2;
        int next = (i + 1) % 2;

        poly[next].clear();
        poly[next].assign(poly[curr].size() + 1, 0);

        for (int j = 0; j < poly[curr].size(); ++j) {
            poly[next][j] += poly[curr][j] * (1 - prob_list[i + 1]);
            poly[next][j + 1] += poly[curr][j] * prob_list[i + 1];
        }

        ++max_score;
        int curr_score = max_score;
        int idx = 0;

        while (curr_score >= t) {
            curr_prob += poly[next][poly[next].size() - 1 - idx];
            curr_score -= 2;
            ++idx;
        }

        if (curr_prob > res) {
            res = curr_prob;
        }
    }
}

void print_result() {
    std::cout << std::fixed << std::setprecision(9) << res << std::endl;
}