Cod sursa(job #606698)

Utilizator CS-meStanca Marian Ciprian CS-me Data 8 august 2011 14:29:08
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define maxn 30001
FILE *fin=fopen("secv3.in","r");
FILE *fout=fopen("secv3.out","w");
int cost[maxn],t[maxn],maxx=-1,ind[maxn],i;
double dec[maxn],sum[maxn];
int l,u,n,start,stop;
double n1,n2;

int mmx(double x){
int st,dr,i,j;
double best=-1000;
	sum[0]=0;
	for(i=1;i<=n;i++)
		sum[i]=sum[i-1]+cost[i]-x*t[i];
	st=0;dr=0;dec[st]=0;ind[st]=0;
	if(sum[l]>best){
		best=sum[l];
		start=1;stop=l;
	}
	for(i=l+1;i<=n;i++){
		if(ind[st]<i-u) st++;
		j=dr;
		while(j>=st&&sum[i-l]<dec[j]) j--;
		dr=j+1;
		dec[dr]=sum[i-l];
		ind[dr]=i-l;
		if(sum[i]-dec[st]>best){
			best=sum[i]-dec[st];
			start=ind[st]+1;
			stop=i;
		}
	}
	if(best>0) return 1;
return 0;
}

void cb(double xmin,double xmax){
double mij;
	while(xmax-xmin>1e-3)
	{
		mij=(xmin+xmax)/2;
		if(mmx(mij)) xmin=mij;
		else xmax=mij;
	}
	fprintf(fout,"%.2f",xmin);
}
int main(){
	fscanf(fin,"%d%d%d",&n,&l,&u);
	for(i=1;i<=n;i++){
		fscanf(fin,"%d",&cost[i]);
		if(maxx<cost[i]) maxx=cost[i];
	}
	for(i=1;i<=n;i++)
		fscanf(fin,"%d",&t[i]);
	fclose(fin);
	//cb(0,maxx);
	fclose(fout);
return 0;
}