Cod sursa(job #1218577)

Utilizator vladrochianVlad Rochian vladrochian Data 11 august 2014 19:40:22
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <fstream>
#include <iomanip>
#include <deque>
#define FOR for(i=1;i<=n;++i)
using namespace std;
int n,l,u,k,a[30005],b[30005];
double v[30005],mn[30005],x,bss=1000,bse=0.001;
deque<pair<double,int>>dq;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int check()
{
	int i;
	FOR
	{
		v[i]=v[i-1]+a[i]-b[i]*x;
		if(!dq.empty())
			if(i-dq.front().second>k)
				dq.pop_front();
		while(!dq.empty())
		{
			if(dq.back().first<v[i])
				break;
			dq.pop_front();
		}
		dq.push_back(make_pair(v[i],i));
		mn[i]=dq.front().first;
	}
	bool eq=0;
	for(i=l;i<=n;++i)
	{
		if(v[i]-mn[i-l]>0)
			return 1;
		if(v[i]==mn[i-l])
			eq=1;
	}
	return eq?0:-1;
}
int main()
{
	int i;
	fin>>n>>l>>u;
	k=u-l;
	FOR
		fin>>a[i];
	FOR
		fin>>b[i];
	FOR
	{
		x=1.0*a[i]/b[i];
		if(x>bse)
			bse=x;
		if(x<bss)
			bss=x;
	}
	while(bse-bss>0.009)
	{
		x=(bss+bse)/2;
		int c=check();
		if(!c)
			break;
		if(c>0)
			bss=x;
		else
			bse=x;
	}
	fout<<setprecision(2)<<fixed<<x;
	return 0;
}