Cod sursa(job #390433)

Utilizator freak93Adrian Budau freak93 Data 3 februarie 2010 18:56:32
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<cstdio>

const char iname[]="secv3.in";
const char oname[]="secv3.out";
const int maxn=30005;

float a[maxn],b[maxn],x,y,eps,mid,s[maxn],eps2;

int n,i,j,q,p,deque[maxn],l,u;

void add(int x)
{
    while(q>=p&&s[deque[q]]>s[x])
        --q;
    deque[++q]=x;
}

int main()
{
    freopen(iname,"r",stdin);
    freopen(oname,"w",stdout);
    scanf("%d%d%d",&n,&l,&u);
    for(i=1;i<=n;++i)
        scanf("%f",&a[i]);
    for(i=1;i<=n;++i)
        scanf("%f",&b[i]);
    eps=1e-5;
    eps2=1e-20;
    x=0.0;
    y=10000.0;
    while(y-x>eps)
    {
        mid=(y+x)/2;
        for(i=1;i<=n;++i)
            a[i]-=mid*b[i];
        for(i=1;i<=n;++i)
            s[i]=s[i-1]+a[i];
        p=1;q=0;
        add(0);
        for(i=l;i<=n;++i)
        {
            while(deque[p]<i-u&&p<=q)
                ++p;
            if(s[i]-s[deque[p]]>=0)
            {
                x=mid;
                break;
            }
            add(i-l+1);
        }
        if(mid-x>eps2)
            y=mid;
        for(i=1;i<=n;++i)
            a[i]+=mid*b[i];
    }

    printf("%.2f\n",mid);
    fclose(stdin);
    fclose(stdout);

    return 0;
}