Cod sursa(job #206460)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 6 septembrie 2008 20:18:01
Problema Secventa 3 Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include<stdio.h>

FILE *fin=fopen("secv3.in","r"),
    *fout=fopen("secv3.out","w");

int N,U,L,c[30005],t[30005];
int dq[30005];
double sol;
int main(){

    fscanf(fin,"%d%d%d",&N,&L,&U);
    fscanf(fin,"%d",&c[1]);
    for(int i=2;i<=N;i++){
        int x;
        fscanf(fin,"%d",&x);
        c[i]=c[i-1]+x;
    }
    fscanf(fin,"%d",&t[1]);
    for(int i=2;i<=N;i++){
        int x;
        fscanf(fin,"%d",&x);
        t[i]=t[i-1]+x;
    }



    int li=1,lf=0;

    for(int i=L;i<=N;i++){
        if(i-dq[li]>=U)
            ++li;

        int j=i-L;
        while(lf>=li && (double) (c[i]-c[j])/(t[i]-t[j])>= (double) c[dq[lf]]/t[dq[lf]])
            --lf;

        dq[++lf]=j;
        if((double) (c[i]-c[dq[li]])/(t[i]-t[dq[li]])>sol)
            sol=(double)(c[i]-c[dq[li]])/(t[i]-t[dq[li]]);
    }

    fprintf(fout,"%.2f\n",sol);
    fclose(fin);
    fclose(fout);
    return 0;

}