Cod sursa(job #804215)

Utilizator Marius96Marius Gavrilescu Marius96 Data 29 octombrie 2012 01:36:30
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<cmath>
#include<deque>
#include<algorithm>
using std::max;
using std::deque;

long long t[30005];
long long c[30005];
long long v[30005];
int n,l,u;

bool isok (long long m)
{	
	for(int i=0;i<n;i++)
		v[i]=v[i-1]+c[i]*100-t[i]*m;

	deque<long long> d;
	if(v[l]>=0)
		return true;
	else{
		for(int i=l;i<n;i++){
			while(d.empty()==false&&v[d.back()]>v[i-l])
				d.pop_back();
			d.push_back (i-l);
			while(d.front()<=i-u-1)
				d.pop_front();
			if(v[i]-v[d.front()]>=0){
				return true;
			}
		}
	}
	return false;
}

int main()
{
	freopen ("secv3.in","r",stdin);
	freopen ("secv3.out","w",stdout);

	scanf ("%d%d%d",&n,&l,&u);

	scanf ("%lld",c);
	for(int i=1;i<n;i++)
		scanf ("%lld",c+i);

	scanf ("%lld",t);
	for(int i=1;i<n;i++)
		scanf ("%lld",t+i);

	long long s=1,e=200000000005;

	while(s<e){
		long long m=(s+e)/2;
		if(m==s)
			m=e;

		if(isok (m))
			s=m;
		else
			e=m-1;
	}
	printf ("%lld.%02lld",s/100,s%100);
	return 0;
}