Cod sursa(job #359660)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 27 octombrie 2009 22:28:53
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#include <algorithm>

int a[30100], b[30100], deque[30100];
long long s[30100];
int st,dr,i,n,mij,l,u;
float sol;

bool ok(int x)
{
	int i,j,st,dr;
	dr=s[0]=0; st=1;
	for (i=1; i<=n; i++){
		s[i]=s[i-1]+a[i]-b[i]*x;
		if (i>=l){
			while (st<=dr && s[deque[dr]]>s[i-l])
				deque[dr--]=0;
			deque[++dr]=i-l;
			if (deque[st]<i-u)
				deque[st++]=0;
			if (s[deque[st]]<=s[i]){
				for (j=st; j<=dr; j++)
					deque[j]=0;
				return true;
			}
		}
	}
	for (i=st; i<=dr; i++)
		deque[i]=0;
	return false;
}

int main()
{
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
	scanf("%d %d %d",&n,&l,&u);
	for (i=1; i<=n; i++){
		scanf("%d",&a[i]);
		a[i]=a[i]*100;
		if (dr<a[i])
			dr=a[i];
	}
	for (i=1; i<=n; i++)
		scanf("%d",&b[i]);
	st=0;
	while (st<=dr){
		mij=(st+dr)/2;
		if (ok(mij)){
			sol=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	}
	sol=sol/100;
	printf("%.2f\n",sol);
	return 0;
}