%你赛的题，模拟赛的时候开数组没算高精度小数类直接开炸了，暴力的60挂没了

去题解里学了个斜优的做法，但是只有73，错的都是只保证误差小于1e-5，个人猜测可能是中间斜优算策略的时候精度挂了，但是看了半天觉得精度又没啥问题。

各位大佬快来帮帮我哇QAQ ，赶紧改完这题就可以去改那个把O看成0挂46分的旷野大计算了

代码如下。

struct node{
    double x,y;
    friend node operator-(const node x,const node y){
        return {x.x-y.x,x.y-y.y};
    }
    friend double operator *(const node x,const node y){
        return x.x*y.y-x.y*y.x;
    }
};
double v[8200],sum[8200];
double dp[2][8200];
int pre[8200][8200];
int n,k,p;
Decimal ANS;
deque<node>q;
inline void ok(int k,int loc,Decimal &x){
    if(!k)return ;
    ok(k-1,pre[k][loc],x);
    x=(x+sum[loc]-sum[pre[k][loc]])/(loc-pre[k][loc]+1);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>k>>p;
    for(int i=1;i<=n;i++)cin>>v[i];
    Decimal op=to_string(v[1]);
    double opt=v[1];
    sort(v+1,v+n+1);
    int loc=n+1;
    for(int i=1;i<=n;i++)
        if(v[i]>opt){loc=i;
            break;
        }
    for(int i=loc;i<=n;i++)
        v[i-loc+1]=v[i]-opt;;
    n=n-loc+1;
    k=min(k,n);
        bool fl=1;
        double nowAs=0;
        int sk=0;
        for(int i=1;i<=n;i++)
            sum[i]=sum[i-1]+v[i];
        for(int i=1;i<=k;i++){
            q.clear();
            q.push_back({(double)(i-2),(double)(sum[i-1]-dp[!fl][i-1])});
            for(int j=i;j<=n;j++){
                node A={(double)(j),(double)(sum[j])};
                while(q.size()>=2&&(A-q[0])*(A-q[1])>0)q.pop_front();
                dp[fl][j]=(A-q.front()).y/(A-q.front()).x;
                pre[i][j]=q.front().x+1;
                node P={(double)(j-1),(double)(sum[j]-dp[!fl][j])};
                while(q.size()>=2&&(P-q[q.size()-2])*(q[q.size()-1]-q[q.size()-2])>0)q.pop_back();
                q.push_back(P);
            }
            if(nowAs<dp[fl][n])nowAs=dp[fl][n],sk=i;
            fl^=1;
        }
        ok(sk,n,ANS);
        op+=ANS;
    cout<<op.to_string(p<<1);