Cod sursa(job #804195)

Utilizator Marius96Marius Gavrilescu Marius96 Data 29 octombrie 2012 00:12:26
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 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;

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

	int s=1,e=1000*100+5;

	while(s<e){
		long long m=(s+e)/2;
		if(m==s)
			m=e;
		for(int i=0;i<n;i++)
			v[i]=v[i-1]+c[i]*100-t[i]*m;

		deque<int> d;
		bool ok=false;
		if(v[l]>=0)
			ok=true;
		else{
			for(int i=l;i<n;i++){
				d.push_back (i-l);
				if(i>u)
					while(d.front()<=i-u)
						d.pop_front();
				if(v[i]-v[d.front()]>=0){
					ok=true;
					break;
				}
			}
		}

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