Cod sursa(job #432912)

Utilizator GotenAmza Catalin Goten Data 2 aprilie 2010 22:56:19
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include<fstream>
#include<math.h>
#include<deque>
#define nmax 30100
using namespace std;
int c[nmax],t[nmax];
double a[nmax],b[nmax];
double st,dr=1000,m,sol;
int main()
{
	int n,l,u,k,i,gasit=0;
	ifstream read ("secv3.in");
	ofstream write ("secv3.out");
	read>>n>>l>>u;
	k=u-l+1;
	for(i=1;i<=n;i++)
		read>>c[i];
	for(i=1;i<=n;i++)
		read>>t[i];
	while(!gasit)
	{
		deque <int> dq;
		m=(st+dr)/2;
		for(i=1;i<=n;i++)
			a[i]=a[i-1]+c[i]-m*t[i];
		dq.push_back(0);
		for(i=1;i<=n;i++)
		{
			while(!dq.empty()&&dq.front()+k<i+1)
				dq.pop_front();
			while(!dq.empty()&&a[dq.back()]>a[i])
				dq.pop_back();
			dq.push_back(i);
			b[i]=a[dq.front()];
		}
		sol=-(1<<30);
		for(i=l;i<=n;i++)
			if(a[i]-b[i-l]>sol)
				sol=a[i]-b[i-l];
		if(fabs(sol)<=0.001)
			gasit=1;
		else
			if(sol<0)
				dr=m;
			else
				st=m;
	}
	write<<m;
	return 0;
}