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
// Author: Bartek Knapik

#include <cstdio>
#include <vector>

using namespace std;

const int MAX_N = 50000 + 9;

double p[MAX_N], tmp[MAX_N];
vector<double> tot[MAX_N];

int n, t;

void sort(int begin, int end)
{
    if (end - begin <= 1)
        return;
    
    int mid = (begin + end) / 2;
    
    sort(begin, mid);
    sort(mid, end);
    
    int a = begin;
    int b = mid;
    int c = 0;
    
    while (a < mid && b < end)
    {
        if (p[a] > p[b]) tmp[c++] = p[a++];
        else tmp[c++] = p[b++];
    }
    
    while (a < mid) tmp[c++] = p[a++];
    while (b < end) tmp[c++] = p[b++];
    
    c = 0;
    
    while (begin < end) p[begin++] = tmp[c++];
}

int main()
{
    scanf("%d%d", &n, &t);
    for (int i = 0; i < n; ++i) scanf("%lf", &p[i]);
    sort(0, n);
    
    for (int i = 0; i <= n; ++i) tot[i].resize(MAX_N);
    for (int i = 0; i <= n; ++i) tot[i][0] = 1.0;
    
    for (int i = 1; i <= n; ++i)
        for (int f = 0; f <= i; ++f)
        {
            tot[i][f] = tot[i-1][f] * p[i-1] ;
            if (f) tot[i][f] += tot[i-1][f-1] * (1 - p[i-1]);
        }
        
        
    double ans, tmp_ans;
    ans = 0.0;
    
    for (int i = t; i <= n; ++i)
    {
        tmp_ans = 0.0;
        for (int f = 0; 2 * f <= i - t; ++f)
            tmp_ans += tot[i][f];
        if (tmp_ans > ans)
            ans = tmp_ans;
    }
    
    printf("%.20lf\n", ans);
    
    return 0;
}