#include<bits/stdc++.h> using namespace std; //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); #define mod 998244353 #define ll long long #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f inline int read() { char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();} int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();} if(nega==-1) return -ans; return ans; } void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);} #define N 50005 using db=long double; const db eps=1e-13; db a[N],f[N],g[N]; int n,t; signed main() { cin>>n>>t; for(int i=1;i<=n;i++) scanf("%Lf",&a[i]); f[0]=1; int l=0,r=0; sort(a+1,a+n+1,greater()); db ans=0; for(int i=1;i<=n;i++) { for(int j=l;j<=r+1;j++) g[j]=0; for(int j=l;j<=r;j++) g[j]+=f[j]*(1-a[i]),g[j+1]+=f[j]*a[i]; for(int j=l;j<=r+1;j++) f[j]=g[j]; // printf("%d %d : ",l,r); // for(int j=l;j<=r;j++) printf("%.2Lf ",f[j]); // cout<<"\n"; db res=0; for(int j=l;j<=r+1;j++) if(j-(i-j)>=t) res+=f[j]; ans=max(ans,res); while(f[l]<eps) l++; r++; while(f[r]<eps) r--; } printf("%.10Lf\n",ans); 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 | #include<bits/stdc++.h> using namespace std; //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); #define mod 998244353 #define ll long long #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f inline int read() { char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();} int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();} if(nega==-1) return -ans; return ans; } void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);} #define N 50005 using db=long double; const db eps=1e-13; db a[N],f[N],g[N]; int n,t; signed main() { cin>>n>>t; for(int i=1;i<=n;i++) scanf("%Lf",&a[i]); f[0]=1; int l=0,r=0; sort(a+1,a+n+1,greater()); db ans=0; for(int i=1;i<=n;i++) { for(int j=l;j<=r+1;j++) g[j]=0; for(int j=l;j<=r;j++) g[j]+=f[j]*(1-a[i]),g[j+1]+=f[j]*a[i]; for(int j=l;j<=r+1;j++) f[j]=g[j]; // printf("%d %d : ",l,r); // for(int j=l;j<=r;j++) printf("%.2Lf ",f[j]); // cout<<"\n"; db res=0; for(int j=l;j<=r+1;j++) if(j-(i-j)>=t) res+=f[j]; ans=max(ans,res); while(f[l]<eps) l++; r++; while(f[r]<eps) r--; } printf("%.10Lf\n",ans); return 0; } |