Cod sursa(job #206818)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 9 septembrie 2008 20:32:41
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>
#define zero 0.0001

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

int U,L,N, c[30005],t[30005];
double a[300005];
int dq[300005];

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

    double li=0,lf=30000000;

    while(lf-li>zero){

        double mij=(li+lf)/2;

        for(int i=1;i<=N;i++)
            a[i]=(double)c[i]-mij*t[i]+a[i-1];


        double sol=-30000000;

        int lli=1,llf=0;

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

            int j=i-L;
            while(llf>=lli && a[j] < a[dq[llf]])
                --llf;

            dq[++llf]=j;

            if(sol < a[i]-a[dq[lli]])
                sol=a[i]-a[dq[lli]];
        }

        if(sol<zero)
            lf=mij;
        else
            li=mij;

    }

    fprintf(fout,"%.2f",li);

    fclose(fin);
    fclose(fout);
    return 0;
}