记录编号	280605	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]最佳序列	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2016-07-10 16:37:25	内存使用	4.13 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
/*
	二分答案。
		我们的二分范围是[0,maxn],其中maxn是数列A中的最大值。
		每次去mid，我们可以用原数列的每一项都减去mid，得到一个新的数列，这个数列中可能有正
	有负，我只需要求在新数列中某一个长度在[L,R]之间的序列之和大于零，证明我的mid取小了，
	反之如果所有满足条件的区间之和都小于零，证明mid取大了。
		至于求和我们可以使用前缀和。用单调队列维护符合情况的左边界来优化。
		具体不详细说了，自己看吧。 
*/
int fate,lucy,windy;
double alice[200010]={0};
double maxn=-1.0;
inline double rider(double a){
	if(a>0)	return a;
	else	return -a;
}
struct ss{
	double nazi;
	int id;
}Tina[200010];

deque<ss> asuna;
double archer(int a,int k){
	while(!asuna.empty()&&asuna.back().nazi>=Tina[a].nazi)	asuna.pop_back();
	asuna.push_back(Tina[a]);
	while(!asuna.empty()&&asuna.front().id<k)	asuna.pop_front();
	return asuna.front().nazi;
}

int main(){
	freopen("bestseq.in","r",stdin);
	freopen("bestseq.out","w",stdout);
	scanf("%d%d%d",&fate,&lucy,&windy);
	int ax;
	for(int i=1;i<=fate;++i){
		scanf("%d",&ax);
		alice[i]=(double)ax;
		//scanf("%lf",&alice[i]);
		if(alice[i]>maxn)	maxn=alice[i];
		//printf("%.4lf ",alice[i]);
		Tina[i].id=i;
	}
	double l=0,r=(double)maxn,mid,q;
	int j;
	bool Luka;
	while(rider(r-l)>1e-7){
		Luka=false;
		mid=(r+l)/2;
	//	printf("\n\n\n%.4lf %.4lf %.4lf\n",l,r,mid);
		while(!asuna.empty())	asuna.pop_front();
		for(int i=1;i<=fate;++i){
			Tina[i].nazi=((double)alice[i])-mid;
	//		printf("%.4lf ",Tina[i].nazi);
			Tina[i].nazi+=Tina[i-1].nazi;
		}
	//	printf("\n");
		for(int i=1;i<=fate;++i){
		//	printf("%d ",alice[i]);
		}
	//	printf("\n");
		for(int i=lucy;i<=fate;++i){
			j=i-lucy;
			q=Tina[i].nazi - archer(j,i-windy);
	//\		printf("%d %.4lf\n",i,q);
			if(q>1e-7){
				Luka=true;
				break;
			}
		}
		if(Luka)	l=mid+1e-7;
		else	r=mid-(1e-7);
	}
	printf("%.4lf",mid);
	return 0;
}