Cod sursa(job #1218590)

Utilizator vladrochianVlad Rochian vladrochian Data 11 august 2014 20:04:34
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 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=5000,bse;
deque<pair<double,int>>dq;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
bool check()
{
	dq.clear();
	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;
	}
	for(i=l;i<=n;++i)
		if(v[i]-mn[i-l]>=0)
			return 1;
	return 0;
}
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.001)
	{
		x=(bss+bse)/2;
		bool c=check();
		if(c)
			bss=x;
		else
			bse=x;
	}
	fout<<setprecision(2)<<fixed<<x<<"\n";
	return 0;
}