Cod sursa(job #389288)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 1 februarie 2010 13:54:18
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include<queue>
#include<stdio.h>
using namespace std;
#define DIM 30010
int n,l,u;
int c[DIM],t[DIM];
double a[DIM];
double calc(double rez)
{
	deque <int> dq;
	dq.push_back(0);
	double Max=-(1<<30);
	for(int i=1;i<=n;i++)
		a[i]=a[i-1]+c[i]-t[i]*rez;
	for(int i=l;i<=n;i++)
	{
		if(a[i]-a[dq.front()]>Max)
			Max=a[i]-a[dq.front()];
		while(!dq.empty()&&a[dq.back()]>=a[i-l+1])
			dq.pop_back();
		dq.push_back(i-l+1);
		if(dq.front()==i-u)
			dq.pop_front();
	}
	return Max;
}
int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
	scanf("%d%d%d",&n,&l,&u);
	for(int i=1;i<=n;i++)
		scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	double st=0,dr=1000,mij,nr;
	while(dr-st>0.001)
	{
		mij=(st+dr)/2;
		nr=calc(mij);
		if(nr==0)
			st=dr=mij;
		else
			if(nr>0)
				st=mij+0.001;
			else
				dr=mij-0.001;
	}
	printf("%.2lf",dr);
	return 0;
}