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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class MariaExamSolver {
public:
    static void resolve() {
        int n, t;
        vector<double> p;
        vector dp(1, 1.0);

        int lo = 0, hi = 0;
        double curMean = 0.0, curVar = 0.0, bestProb = 0.0;

        cin >> n >> t;
        p.resize(n);

        for (int i = 0; i < n; i++) {
            cin >> p[i];
        }

        bucketSort(p);

        for (int k = 1; k <= n; k++) {
            double pk = p[k - 1];
            double newMean = curMean + pk;
            double newVar = curVar + pk * (1 - pk);
            double sd = (newVar > 0 ? sqrt(newVar) : 0.0);

            int margin = (sd > 0 ? (int) ceil(10 * sd) : 0);

            int new_min = lo;
            int new_max = hi + 1;

            int window_lo = max(new_min, (int) floor(newMean - margin));
            int window_hi = min(new_max, (int) ceil(newMean + margin));
            int newSize = window_hi - window_lo + 1;

            vector new_dp(newSize, 0.0);
            double addLow = 0.0, addHigh = 0.0;


            for (int x = lo; x <= hi; x++) {
                double prob = dp[x - lo];
                int new_x = x;
                if (new_x < window_lo)
                    addLow += prob * (1 - pk);
                else if (new_x > window_hi)
                    addHigh += prob * (1 - pk);
                else
                    new_dp[new_x - window_lo] += prob * (1 - pk);

                new_x = x + 1;
                if (new_x < window_lo)
                    addLow += prob * pk;
                else if (new_x > window_hi)
                    addHigh += prob * pk;
                else
                    new_dp[new_x - window_lo] += prob * pk;
            }
            new_dp[0] += addLow;
            new_dp[newSize - 1] += addHigh;

            dp.swap(new_dp);
            lo = window_lo;
            hi = window_hi;
            curMean = newMean;
            curVar = newVar;

            if (k >= t) {
                int needed = (t + k + 1) / 2;
                double passProb = 0.0;
                if (needed <= hi) {
                    for (int x = max(needed, lo); x <= hi; x++) {
                        passProb += dp[x - lo];
                    }
                }
                bestProb = max(bestProb, passProb);
            }
        }

        cout << fixed << setprecision(20) << bestProb << endl;
    }

private:
    static void bucketSort(vector<double> &arr) {
        const int n = arr.size();
        if (n <= 1) return;

        constexpr int bucketCount = 1000;
        vector<vector<double> > buckets(bucketCount);
        for (int i = 0; i < n; i++) {
            const int index = min(bucketCount - 1, (int) (arr[i] * bucketCount));
            buckets[index].push_back(arr[i]);
        }
        for (int i = 0; i < bucketCount; i++) {
            ranges::sort(buckets[i], greater<double>());
        }
        int pos = 0;
        for (int i = bucketCount - 1; i >= 0; i--) {
            for (double val: buckets[i]) {
                arr[pos++] = val;
            }
        }
    }
};

int main() {
    MariaExamSolver::resolve();
    return 0;
}