#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=5e4+7; int ile[LIM]; ld T[LIM], wynik[LIM]; vector<ld>tr[4*LIM]; using cd = complex<ld>; const ld PI = acos(-1); void fft(vector<cd> & a, bool invert) { int n = a.size(); for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { ld ang = 2 * PI / len * (invert ? -1 : 1); cd wlen(cos(ang), sin(ang)); for (int i = 0; i < n; i += len) { cd w(1); for (int j = 0; j < len / 2; j++) { cd u = a[i+j], v = a[i+j+len/2] * w; a[i+j] = u + v; a[i+j+len/2] = u - v; w *= wlen; } } } if (invert) { for (cd & x : a) x /= n; } } vector<ld>mnoz(vector<ld>A, vector<ld>B) { int n=1; while(n<A.size()+B.size()) n*=2; vector<cd>fA(n), fB(n); rep(i, A.size()) fA[i]=A[i]; rep(i, B.size()) fB[i]=B[i]; fft(fA, false); fft(fB, false); rep(i, n) fA[i]*=fB[i]; fft(fA, true); vector<ld>C(A.size()+B.size()-1); rep(i, C.size()) C[i]=fA[i].real(); return C; } void licztr(int v, int l, int r) { if(l==r) { tr[v]={(ld)1-T[l], T[l]}; return; } int mid=(l+r)/2; licztr(2*v, l, mid); licztr(2*v+1, mid+1, r); tr[v]=mnoz(tr[2*v], tr[2*v+1]); } void solve(int v, int l, int r, vector<ld>&P) { int dl=r-l+1, prz=max(ile[l]-dl, 0); if(l==r) { if(ile[l]-prz>=0 && ile[l]-prz<P.size()) wynik[l]+=P[ile[l]-prz]*((ld)1-T[l]); if(ile[l]-1-prz>=0 && ile[l]-1-prz<P.size()) wynik[l]+=P[ile[l]-1-prz]*T[l]; return; } int mid=(l+r)/2; // [l, mid] chce dostac ile[l]-d/2, ile[mid] vector<ld>A; rep(i, P.size()) if(ile[l]-(mid-l+1)<=prz+i && prz+i<=ile[mid]) A.pb(P[i]); solve(2*v, l, mid, A); vector<ld>B=mnoz(P, tr[2*v]); // [mid+1, r] chce dostac ile[mid+1]-d/2, ile[r] vector<ld>C; rep(i, B.size()) if(ile[mid+1]-(r-mid)<=prz+i && prz+i<=ile[r]) C.pb(B[i]); solve(2*v+1, mid+1, r, C); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, t; cin >> n >> t; for(int i=1; i<=n; ++i) { if(i>=t) ile[i-1]=(i+t+1)/2; else ile[i-1]=i; ile[i-1]=i-ile[i-1]; } rep(i, n) { cin >> T[i]; T[i]=(ld)1-T[i]; } sort(T, T+n); licztr(1, 0, n-1); vector<ld>P(ile[n-1]+1, 1); solve(1, 0, n-1, P); ld ans=0; rep(i, n) if(i+1>=t) ans=max(ans, wynik[i]); cout << fixed << setprecision(7) << ans << '\n'; }
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 115 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define rep(a, b) for(int a = 0; a < (b); ++a) #define st first #define nd second #define pb push_back #define all(a) a.begin(), a.end() const int LIM=5e4+7; int ile[LIM]; ld T[LIM], wynik[LIM]; vector<ld>tr[4*LIM]; using cd = complex<ld>; const ld PI = acos(-1); void fft(vector<cd> & a, bool invert) { int n = a.size(); for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { ld ang = 2 * PI / len * (invert ? -1 : 1); cd wlen(cos(ang), sin(ang)); for (int i = 0; i < n; i += len) { cd w(1); for (int j = 0; j < len / 2; j++) { cd u = a[i+j], v = a[i+j+len/2] * w; a[i+j] = u + v; a[i+j+len/2] = u - v; w *= wlen; } } } if (invert) { for (cd & x : a) x /= n; } } vector<ld>mnoz(vector<ld>A, vector<ld>B) { int n=1; while(n<A.size()+B.size()) n*=2; vector<cd>fA(n), fB(n); rep(i, A.size()) fA[i]=A[i]; rep(i, B.size()) fB[i]=B[i]; fft(fA, false); fft(fB, false); rep(i, n) fA[i]*=fB[i]; fft(fA, true); vector<ld>C(A.size()+B.size()-1); rep(i, C.size()) C[i]=fA[i].real(); return C; } void licztr(int v, int l, int r) { if(l==r) { tr[v]={(ld)1-T[l], T[l]}; return; } int mid=(l+r)/2; licztr(2*v, l, mid); licztr(2*v+1, mid+1, r); tr[v]=mnoz(tr[2*v], tr[2*v+1]); } void solve(int v, int l, int r, vector<ld>&P) { int dl=r-l+1, prz=max(ile[l]-dl, 0); if(l==r) { if(ile[l]-prz>=0 && ile[l]-prz<P.size()) wynik[l]+=P[ile[l]-prz]*((ld)1-T[l]); if(ile[l]-1-prz>=0 && ile[l]-1-prz<P.size()) wynik[l]+=P[ile[l]-1-prz]*T[l]; return; } int mid=(l+r)/2; // [l, mid] chce dostac ile[l]-d/2, ile[mid] vector<ld>A; rep(i, P.size()) if(ile[l]-(mid-l+1)<=prz+i && prz+i<=ile[mid]) A.pb(P[i]); solve(2*v, l, mid, A); vector<ld>B=mnoz(P, tr[2*v]); // [mid+1, r] chce dostac ile[mid+1]-d/2, ile[r] vector<ld>C; rep(i, B.size()) if(ile[mid+1]-(r-mid)<=prz+i && prz+i<=ile[r]) C.pb(B[i]); solve(2*v+1, mid+1, r, C); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, t; cin >> n >> t; for(int i=1; i<=n; ++i) { if(i>=t) ile[i-1]=(i+t+1)/2; else ile[i-1]=i; ile[i-1]=i-ile[i-1]; } rep(i, n) { cin >> T[i]; T[i]=(ld)1-T[i]; } sort(T, T+n); licztr(1, 0, n-1); vector<ld>P(ile[n-1]+1, 1); solve(1, 0, n-1, P); ld ans=0; rep(i, n) if(i+1>=t) ans=max(ans, wynik[i]); cout << fixed << setprecision(7) << ans << '\n'; } |