Maximize Rating
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5050;
double f[N][N];
int a[N];
/*
选多少?都有可能,就去枚举
选哪些数? 有大量重叠的子问题,dp
*/
signed main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
double ans=-1e8;
double sum[N];
sum[1]=1;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]*0.9+1;
f[0][0]=0;
f[1][1]=a[1];
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
if(j==1)
f[i][j]=max(f[i-1][j],(double)a[i]);
else if(j<i)
f[i][j]=max(f[i-1][j-1]*0.9+a[i],f[i-1][j]);
else
f[i][j]=f[i-1][j-1]*0.9+a[i];
}
}
for(int i=1;i<=n;i++)
ans=max(ans,f[n][i]/sum[i]-1200*1.0/sqrt(i));
cout<<fixed<<setprecision(10)<<ans<<endl;
}
25/3/15