Cod sursa(job #2924693)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 8 octombrie 2022 18:18:09
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
//Ilie Dumitru
#include<cstdio>
#include<algorithm>

const int NMAX=30005;
int N, L, U, c[NMAX], t[NMAX];
double aux[NMAX]/*=Suma pt j=0,i din c[j]-T*t[j]*/;
int dq[NMAX], st, end;

bool is_doable(double T)
{
    int i;
    aux[0]=0;
    for(i=0;i<N;++i)
        aux[i+1]=aux[i]+c[i]-t[i]*T;

    st=0, end=1;
    dq[0]=0;
    /*
    sc
    -- >= T
    st

    sc-st*T>=0
    aux[i]-aux[j]>=0
    */
    if(aux[L]>=0)
        return 1;
    for(i=L;i<N;++i)
    {
        while(dq[st]<=i-U && st<end)
            ++st;
        while(st<end && aux[dq[end-1]]>=aux[i-L+1])
            --end;
        dq[end++]=i-L+1;
        if(aux[i+1]-aux[dq[st]]>=0)
            return 1;
    }
    return 0;
}

int main()
{
    FILE* f=fopen("secv3.in", "r"), *g=fopen("secv3.out", "w");
    int i;
    double l=0.001, r=1000, m;

    fscanf(f, "%d%d%d", &N, &L, &U);
    for(i=0;i<N;++i)
        fscanf(f, "%d", c+i);
    for(i=0;i<N;++i)
        fscanf(f, "%d", t+i);
    fclose(f);

    for(i=0;i<20;++i)
    {
        m=(l+r)*0.5;
        if(is_doable(m))
            l=m;
        else
            r=m;
    }

    i=l*100;
    fprintf(g, "%d.%02d", i/100, i%100);
    fclose(g);

    return 0;
}