Cod sursa(job #1733290)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 24 iulie 2016 13:16:47
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#define MaxN 30001
#define INF 2000000000
#define time second
#define value first
#define var 0.001
using namespace std;

pair <int,int> v[MaxN];
int N,U,L;
double S[MaxN]={},lw,hi,mid,Sol;
deque <int>D;
bool Verify(double val)
{
	for(int i=1;i<=N;i++)
		S[i]=S[i-1]+v[i].value-v[i].time*val;
	double Max=-INF;
	D.clear();
	for(int i=L;i<=N;i++)
	{
		while(!D.empty()&&S[D.back()]>=S[i-L])
			D.pop_back();
		D.push_back(i-L);
		while(D.front()<=i-U)
			D.pop_front();
		if(Max<S[i]-S[D.front()])
			Max=S[i]-S[D.front()];
	}
	if(Max>=0)
		return true;
	else return false;
}
int main()
{
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
	scanf("%d%d%d",&N,&L,&U);
	v[0].value=v[0].time=0;
	for(int i=1;i<=N;i++)
		scanf("%d",&v[i].value);
	for(int i=1;i<=N;i++)
		scanf("%d",&v[i].time);
	lw=0,hi=1001,mid;
	while(lw<=hi)
	{
		mid=(lw+hi)/2;
		if(Verify(mid))
		{
			Sol=mid;
			lw=mid+var;
		}
		else hi=mid-var;
	}
	printf("%lf",Sol);
	return 0;
}