题目分析

性质：

1. 所有积水高度小于等于 1 号点的点可以直接丢掉。
   所以，将留下来的水的高度都改成其原本的高度-1 号点高度，最后答案再加上 1 号点的高度。
2. 假如被要求进行两次合并，有两杯水 $h _ 1<h _ 2$，则一定先合并低的，再合并高的。
   证明：先合并低的：$\frac{1}{2}(\frac{1}{2} h _ 1+ h _ 2)=\frac{1}{4} h _ 1+\frac{1}{2} h _ 2$，先合并高的：$\frac{1}{2} h _ 1 + \frac{1}{4} h _ 2$。
3. 若有一部分水合并了，一部分没有，那么被合并的水一定是最高的几杯。

将所有留下来的水从低到高排序，设 $h _ i$表示第 $i$杯水的高度，$s _ i$表示前 $i$杯水的高度前缀和。

合并操作一定是堆在最后面的一段一段的区间，从前往后合并。

设 $f(i,j)$表示前 $j$杯水合并了 $i$次。

$f(i,j)=max(\frac{f(i-1,k)+s _ j-s _ k}{j-k+1})$

观察这个式子，发现是点 $(k-1,s _ k – f(i-1,k))$和点 $(j, s _ j)$构成的直线的斜率。

用单调队列维护点 $(k-1,s _ k – f(i-1,k))$构成的下凸壳。因为点 $(j, s _ j)$的 y 坐标随 x 坐标递增，所以找最优决策时，将队首一段不会构成最优决策的点的弹出，队首就是最优决策。

代码

那个 600 多行的高精度小数类就直接删掉了……只要记得将开头的 const int PREC=后面的数字改为 3000 以上即可。

将每一步的决策用 short 记录下来，然后用高精度小数类再算一次答案。

using namespace std;
#define RI register int
typedef long double db;
typedef long long LL;
const int N=8005;
Decimal ans;
int orzyyb,n,K,P,kpos;db kans;
int h[N],qid[N];LL s[N];short las[N][N];db f[2][N];
struct point{db x,y;}que[N];
point operator - (point A,point B) {return (point){A.x-B.x,A.y-B.y};}
db operator * (point A,point B) {return A.x*B.y-B.x*A.y;}

Decimal getans(int x,int y) {
    if(x==0) return 0;
    return (getans(x-1,las[x][y])+s[y]-s[las[x][y]])/(y-las[x][y]+1);
}

int main() {
    scanf("%d%d%d",&orzyyb,&K,&P);
    scanf("%d",&h[0]);
    for(RI i=1;i<orzyyb;++i) {
        int x;scanf("%d",&x);
        if(x>h[0]) h[++n]=x-h[0];
    }
    sort(h+1,h+1+n);
    for(RI i=1;i<=n;++i) s[i]=s[i-1]+h[i];
    if(K>n) K=n;
    for(RI i=1,t=1;i<=K;++i,t^=1) {
        int he=1,ta=1;
        que[1]=(point){(db)i-2,(db)s[i-1]-f[t^1][i-1]},qid[1]=i-1;
        for(RI j=i;j<=n;++j) {
            point P=(point){(db)j,(db)s[j]};
            while(he<ta&&(P-que[he+1])*(P-que[he])<0) ++he;
            las[i][j]=qid[he],f[t][j]=(db)(P.y-que[he].y)/(db)(P.x-que[he].x);
            P=(point){(db)j-1,(db)s[j]-f[t^1][j]};
            while(he<ta&&(que[ta]-que[ta-1])*(P-que[ta-1])<0) --ta;
            ++ta,que[ta]=P,qid[ta]=j;
        }
        if(f[t][n]>=kans) kans=f[t][n],kpos=i;
    }
    ans=getans(kpos,n)+h[0];
    cout<<ans.to_string(P<<1)<<endl;
    return 0;
}