萌新妹子D可AC的假做法求hack

赛时：队友提了一嘴三分，噼里啪啦敲出代码居然A了，求hack或证明正确性

考虑分治，求出一个区间内选i场比赛的最大值，合并两个区间的时候我们猜测其是一个单峰函数，直接三分，莫名其妙就A了

#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=(b);a<=(c);a++)
#define vi vector<int>
#define pb push_back
#define vld vector<long double>
#define ld long double
using namespace std;

template<class T>inline void read(T &x) {
	T f=1; x=0; char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}

const int N=1e5;
const ld eps=1e-12;

ld pw[N+5],k,k1,r0,p[N+5];

int n,m;

inline vld cdq(int l,int r) {
	if(l==r) {
		vld tmp;
		tmp.pb(0.0);
		tmp.pb(k*p[l]);
		return tmp;
	}
	int mid=((l+r)>>1);
	vld L=cdq(l,mid),R=cdq(mid+1,r);
	vld ans;
	ans.pb(0);
	rep(i,1,r-l+1) {
		int LL=max(0,i-(r-mid)),RR=min(i,mid-l+1),lmid,rmid;
		while((RR-LL)>10) {
			lmid=LL+((RR-LL+1)/3);
			rmid=RR-((RR-LL+1)/3);
			ld lv=R[i-lmid]+L[lmid]*pw[i-lmid];
			ld rv=R[i-rmid]+L[rmid]*pw[i-rmid];
			if((lv-rv)<eps) LL=lmid;
			else RR=rmid;
		}
		ld Max=0.0;
		rep(j,LL,RR) {
			ld V=R[i-j]+L[j]*pw[i-j];
			if((V-Max)>eps) Max=V;
		}
		ans.pb(Max);
	}
	return ans;
}

inline void solve() {
	read(n); read(m); scanf("%Lf %Lf",&k,&r0);
	k1=(1.0-k);
	rep(i,1,n) scanf("%Lf",&p[i]);
	pw[0]=1.0;
	rep(i,1,n) pw[i]=pw[i-1]*k1;
	rep(i,1,n-m) r0*=k1;
	vld ans=cdq(1,n);
	ld Ans=0.0;
	rep(i,n-m,n) {
		ld nans=ans[i]+r0;
		if((nans-Ans)>eps) Ans=nans;
		r0*=k1;
	}
	printf("%.12Lf\n",Ans);
}

int main() {
	int T; read(T); while(T--)
	solve();
}