#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define piii pair<pair<int, int>, int> #define st first.first #define nd first.second #define rd second #define For(i, l, r) for (int i = l; i <= r; i++) #define Forcin(l, r, a) \ for (int i = l; i <= r; i++) \ cin >> a[i]; #define Ford(i, l, r) for (int i = l; i >= r; i--) #define ben(v) v.begin(), v.end() #define LOCAL 0 #define LOCAL2 0 //#define double long double using namespace std; const int M = 1000005, inf = 1e9; int n, t; double dp[M], p[M]; bool comp(double a, double b) { return a > b; } signed main() { cin.tie(0)->sync_with_stdio(); if (LOCAL) freopen("tests/10.in", "r", stdin); if (LOCAL2) freopen("local_out.txt", "w", stdout); cin >> n >> t; For(i, 1, n) cin >> p[i]; sort(p + 1, p + n + 1, comp); dp[n] = 1; double maxi = 0; vector<double> ress; ress.push_back(0); For(i, 1, n) { double cur_win_prob = 0, pi=p[i],rpi=(1-p[i]); int en=n+i; bool par=(t%2-i%2)!=0; for (int j = max(n - i, t - n + i-t%2); j <= en; j += 2) dp[j] = pi * dp[j - 1] + rpi * dp[j + 1]; for (int j = n + t + par; j <= en; j += 2) cur_win_prob += dp[j]; maxi = max(cur_win_prob, maxi); ress.push_back(maxi); } cout << fixed << setprecision(7); cout << maxi; }
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 | #include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define piii pair<pair<int, int>, int> #define st first.first #define nd first.second #define rd second #define For(i, l, r) for (int i = l; i <= r; i++) #define Forcin(l, r, a) \ for (int i = l; i <= r; i++) \ cin >> a[i]; #define Ford(i, l, r) for (int i = l; i >= r; i--) #define ben(v) v.begin(), v.end() #define LOCAL 0 #define LOCAL2 0 //#define double long double using namespace std; const int M = 1000005, inf = 1e9; int n, t; double dp[M], p[M]; bool comp(double a, double b) { return a > b; } signed main() { cin.tie(0)->sync_with_stdio(); if (LOCAL) freopen("tests/10.in", "r", stdin); if (LOCAL2) freopen("local_out.txt", "w", stdout); cin >> n >> t; For(i, 1, n) cin >> p[i]; sort(p + 1, p + n + 1, comp); dp[n] = 1; double maxi = 0; vector<double> ress; ress.push_back(0); For(i, 1, n) { double cur_win_prob = 0, pi=p[i],rpi=(1-p[i]); int en=n+i; bool par=(t%2-i%2)!=0; for (int j = max(n - i, t - n + i-t%2); j <= en; j += 2) dp[j] = pi * dp[j - 1] + rpi * dp[j + 1]; for (int j = n + t + par; j <= en; j += 2) cur_win_prob += dp[j]; maxi = max(cur_win_prob, maxi); ress.push_back(maxi); } cout << fixed << setprecision(7); cout << maxi; } |