327-E.cpp

#include<bits/stdc++.h>
using namespace std;
int n;
double dp[5001][5001];
double a[5001];
double nine[5001];
void init()
{
    nine[0]=1;
    for(int i=1;i<=n;i++)
    {
        nine[i]=nine[i-1]*0.9;
    }
}
double maxn(double a,double b)
{
    if(b-a>(1e-6))return b;
    else return a;
}
int main()
{
    cin>>n;
    init();
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dp[i][j]=maxn(dp[i-1][j-1]*0.9+a[i],dp[i-1][j]);
        }
    }
    double ans=-1e10;
    for(int i=1;i<=n;i++)
    {
        ans=maxn(dp[n][i]/(10-10*nine[i])-(1200/sqrt(i)),ans);
    }
    cout<<fixed<<setprecision(15)<<ans<<endl;
    system("pause");
    return 0;
}