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

using namespace std;

typedef __uint64_t real;

#define MAX 50010
#define ZERO 50010
#define ONE_BITS 64


int n,t;
real ONE;

real b[2][2*MAX+10],p, result,t_result;
int bi=0,bj=1;
real P[MAX];

#define D(x)  

D(
void print(int idx) {
    int l = 8;
    for(int i=-l+ZERO;i<=ZERO+l;i++) 
        printf("%f ", double(b[idx][i])/ONE);
    printf("\n");
})


int main() {
    ONE = 18446744073709551615ULL;

    cin >> n >> t;
    for(int k=0;k<n;k++) { 
        double x;
        cin >> x;
        P[k] = x * ONE;
    }
    sort(&P[0],&P[n], std::greater<>());

    b[bi][ZERO] = ONE;
    D(print(bi));
    int przedz = 0, przedz_d=0, from;
    for(int k=0;k<n;k++) {
        p = P[k];
        przedz_d = max(ZERO-przedz,ZERO-n+t+przedz-2);
        
        from = przedz_d;
        if ((from & 1) != bi) from++;
        b[bj][from-1] = 0;
        for(int i=from;i<=ZERO+przedz;i+=2) {
            real w = b[bi][i];
            real v = (__uint128_t(p) * w) >> ONE_BITS;
            b[bj][i+1]  = v;
            b[bj][i-1] += w-v;
        }
        for(int i=from;i<=ZERO+przedz;i+=2) 
        D(print(bj));
        t_result = 0;
        from = ZERO+t;
        if ((from & 1) != bj) from++;
        for(int i=from;i<=ZERO+przedz+1;i+=2)  t_result+=b[bj][i];
        przedz++;
        result = max(result, t_result);
        swap(bi,bj);
    }
    double r = double(result)/ONE;
    printf("%.9f\n",r);
}