Cod sursa(job #1250397)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 28 octombrie 2014 01:40:21
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<cstdio>
#include<cmath>
#define eps 0.001
int n,i,j,l,r,d[30100];
double smax,p,u,mid,c[30100],t[30100],x[30100];
FILE *f,*g;
int ec(double a){
    int i,p,u;
    double amax;
    for(i=1;i<=n;i++)
        x[i]=x[i-1]+c[i]-t[i]*a;
    p=u=1;
    amax=x[l];
    d[1]=1;
    for(i=l+1;i<=n;i++){
        if(d[p]==i-r-1)
            p++;
        while(p<=u&&x[i-l]<=x[d[u]])
            u--;
        d[++u]=i-l;
        if(amax<=x[i]-x[d[p]]);
            amax=x[i]-x[d[p]];
    }
    return amax>=0;
}
int main(){
    f=fopen("secv3.in","r");
    g=fopen("secv3.out","w");
    fscanf(f,"%d%d%d",&n,&l,&r);
    for(i=1;i<=n;i++){
        fscanf(f,"%lf",&c[i]);
    }
    for(i=1;i<=n;i++){
        fscanf(f,"%lf",&t[i]);
    }
    p=0;
    u=2000000000;
    while(u-p>=eps){
        mid=(p+u)/2;
        if(ec(mid)){
            p=mid+eps;
        }
        else
            u=mid-eps;
    }
    fprintf(g,"%.2lf",u);

    fclose(f);
    fclose(g);
    return 0;
}