Cod sursa(job #359628)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 27 octombrie 2009 21:34:08
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <stdio.h>
#include <algorithm>

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

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