Cod sursa(job #999449)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 20 septembrie 2013 14:26:14
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<fstream>
#include<deque>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,L,U,cost[30100],timp[30100];
double v[30100],sum[30100];
deque <int> D;

inline bool Posibil(double X)
{
	int i;
	double best=-2000000000.0;
	sum[0]=0.0;
	for(i=1;i<=n;i++)
	{
		v[i]=1.0*cost[i]-1.0*timp[i]*X;
		sum[i]=sum[i-1]+v[i];
	}
	D.clear();
	for(i=L;i<=n;i++)
	{
		while(D.size() && sum[D.back()]>=sum[i-L])
			D.pop_back();
		D.push_back(i-L);
		while(D.front()<i-U)
			D.pop_front();
		best=max(best,sum[i]-sum[D.front()]);
	}
	if(best>=0.0)
		return true;
	return false;
}

inline double CautareBinara()
{
	double st,dr,mij,rez=0.0;
	st=0.0;
	dr=1000.0;
	while(dr-st>0.00001)
	{
		mij=(st+dr)/2.0;
		if(Posibil(mij))
		{
			rez=mij;
			st=mij;
		}
		else
			dr=mij;
	}
	return rez;
}

int main()
{
	int i;
	ifstream fin("secv3.in");
	fin>>n>>L>>U;
	for(i=1;i<=n;i++)
		fin>>cost[i];
	for(i=1;i<=n;i++)
		fin>>timp[i];
	fin.close();
	
	freopen("secv3.out","w",stdout);
	printf("%.3lf\n",CautareBinara());
	return 0;
}