Cod sursa(job #804214)

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

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

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

	deque<int> 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 ("%d",c);
	for(int i=1;i<n;i++){
		scanf ("%d",c+i);
//		c[i]+=c[i-1];
	}

	scanf ("%d",t);
	for(int i=1;i<n;i++){
		scanf ("%d",t+i);
//		t[i]+=t[i-1];
	}

	long long s=1,e=1000000LL*100+5;

	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;
}