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
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>

using namespace std;

namespace {
constexpr bool DEBUG = false;
} // namespace

auto main() -> int {
    std::ios_base::sync_with_stdio(false);

    // NOLINTBEGIN(readability-identifier-length)
    int t = 0;
    int n = 0;
    float p = 0;
    // NOLINTEND(readability-identifier-length)
    vector<float> questions;
    vector<float> results;
    vector<float> lastResults;
    cin >> n >> t;
    questions.reserve(n);
    for (int i = 0; i < n; i++) {
        cin >> p;
        questions.push_back(p);
    }
    sort(questions.rbegin(), questions.rend());
    if (DEBUG) {
        for (auto node : questions) {
            cout << node << " ";
        }
        cout << "\n";
    }
    int answered = t - 1;
    /*while (true) {
        if (answered + 2 >= n) {
            break;
        }
        if (questions[answered + 1] < 1 - questions[answered + 2]) {
            break;
        }
        answered += 2;
    }
    answered++;*/
    answered = n;
    if (DEBUG) {
        cout << answered << "\n";
    }
    results.assign((answered * 2) + 1, 0);
    results[answered] = 1;
    float midResult = 0;
    float midResult1 = 0;
    float midResult2 = 0;
    float midResult3 = 0;

    float finalResult = 0;
    for (int i = 0; i < answered; i++) {
        lastResults = std::move(results);
        results.clear();
        results.assign((answered * 2) + 1, 0);
        midResult3 = midResult2;
        midResult2 = midResult1;
        midResult1 = midResult;
        midResult = 0;
        for (int j = answered - i; j <= answered + i; j++) {
            if (j >= answered + t) {
                midResult += lastResults[j];
            }
            results[j - 1] += (1 - questions[i]) * lastResults[j];
            results[j + 1] += questions[i] * lastResults[j];
        }
        finalResult = max(midResult, finalResult);
        if (midResult < midResult2 && midResult1 < midResult3) {
            break;
        }
    }
    midResult = finalResult;
    finalResult = 0;
    for (int i = answered + t; i <= 2 * answered; i++) {
        finalResult += results[i];
    }
    if (finalResult < 0) {
        finalResult = -finalResult;
    }
    finalResult = max(midResult, finalResult);
    cout << std::setprecision(7) << std::fixed << finalResult;
}