Cod sursa(job #1250530)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 28 octombrie 2014 12:03:52
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 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;
    x[0]=0;
    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(x[i]-x[d[p]]>amax)
            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;
}