Cod sursa(job #229275)

Utilizator galacticaBattlestar galactica Data 9 decembrie 2008 20:08:54
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#define N 30100
double deq[N],cost[N],timp[N];
int poz[N];
int main(){
	freopen("secv3.in","r",stdin);
	freopen("secv3.out","w",stdout);
	int n,l,u,i,a,b;
	double max,s;
	scanf("%d%d%d",&n,&l,&u);
	for(i=1;i<=n;++i){
		scanf("%lf",&cost[i]);
		cost[i]+=cost[i-1];
	}
	for(i=1;i<=n;++i){
		scanf("%lf",&timp[i]);
		timp[i]+=timp[i-1];
	}
	a=b=0;
	max=cost[l]/timp[l];
	for(i=l+1;i<=n;++i){
		if(poz[a]<i-u)
			++a;
		s=cost[i-l]/timp[i-l];
		while(b>=a && s>deq[b])
			--b;
		deq[++b]=s;
		poz[b]=i-l;
		if(a>b)
			b=a;
		s=(cost[i]-cost[poz[a]]) / (timp[i]-timp[poz[a]]);
		if(max<s)
			max=s;
	}
	printf("%.2lf\n",max);
	fclose(stdin);
	fclose(stdout);
	return 0;
}