#include <bits/stdc++.h> using i64 = long long; using u64 = unsigned long long; using u32 = unsigned; using u128 = unsigned __int128; constexpr int B = 670; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, t; std::cin >> n >> t; std::vector<double> p(n); for (int i = 0; i < n; i++) { std::string s; std::cin >> s; p[i] = std::stod(s); } std::sort(p.begin(), p.end(), std::greater()); std::vector<double> dp(n + 1); dp[0] = 1; double ans = 0; double sum = 0; for (int i = 0; i < n; i++) { int L = std::max(0, int(sum - B)); int R = std::min(i, int(sum + B)); for (int j = R; j >= L; j--) { dp[j + 1] += dp[j] * p[i]; dp[j] *= (1 - p[i]); } dp[L] += p[i]; if (i + 1 >= t) { ans = std::max(ans, dp[(i + 2 + t) / 2]); } sum += p[i]; } std::cout << std::fixed << std::setprecision(10) << ans << "\n"; return 0; }
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 | #include <bits/stdc++.h> using i64 = long long; using u64 = unsigned long long; using u32 = unsigned; using u128 = unsigned __int128; constexpr int B = 670; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, t; std::cin >> n >> t; std::vector<double> p(n); for (int i = 0; i < n; i++) { std::string s; std::cin >> s; p[i] = std::stod(s); } std::sort(p.begin(), p.end(), std::greater()); std::vector<double> dp(n + 1); dp[0] = 1; double ans = 0; double sum = 0; for (int i = 0; i < n; i++) { int L = std::max(0, int(sum - B)); int R = std::min(i, int(sum + B)); for (int j = R; j >= L; j--) { dp[j + 1] += dp[j] * p[i]; dp[j] *= (1 - p[i]); } dp[L] += p[i]; if (i + 1 >= t) { ans = std::max(ans, dp[(i + 2 + t) / 2]); } sum += p[i]; } std::cout << std::fixed << std::setprecision(10) << ans << "\n"; return 0; } |