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
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

const int DP_SIZE = 100030;
const int DP_OFFSET = 50010;

double prev_dp[DP_SIZE], curr_dp[DP_SIZE];

double sq(double x) {
    return x * x;
}


int main() {
    int questions, min_points;
    double inp;
    scanf("%d%d", &questions, &min_points);
    vector<double> probab;
    for (int i = 0; i < questions; i++) {
        scanf("%lf", &inp);
        probab.push_back(inp);
    }
    for (int i = 0 ; i <= DP_OFFSET; i++) {
        curr_dp[i] = 1;
        prev_dp[i] = 1;
    }
    

    double best_probab = 0;

    sort(probab.begin(), probab.end());
    int min_score = 0;
    int max_score = 0;
    for (int question_idx = probab.size() - 1; question_idx >= 0; question_idx--) {
        swap(prev_dp, curr_dp);
        min_score--;
        max_score++;
        for (int new_score = min_score; new_score <= max_score; new_score++) {
            curr_dp[DP_OFFSET + new_score] =
                prev_dp[DP_OFFSET + new_score - 1] * probab[question_idx] +
                prev_dp[DP_OFFSET + new_score + 1] * (1 - probab[question_idx]);
        }
        if (curr_dp[DP_OFFSET + min_points] > best_probab) {
            best_probab = curr_dp[DP_OFFSET + min_points];
        }
    }

    printf("%.10lf\n", best_probab);
}