Cod sursa(job #488576)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 29 septembrie 2010 14:17:25
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>

#define eps 0.01
#define nmax 30005

int v1[nmax],v2[nmax];
double v3[nmax],s[nmax];
int dq[nmax];
int n,l,u;

int merge(double val)
{
    int i,inc=1,sf=0;
    for(i=1;i<=n;i++)
        v3[i]=v1[i]-val*v2[i];
    for(i=1;i<=n;i++)
        s[i]=s[i-1]+v3[i];
        
    for(i=l;i<=n;i++)
    {
        if(inc<=sf && dq[inc]==i-u)
            inc++;
        while(sf>=inc && s[i-l]<s[dq[sf]])
            sf--;
        dq[++sf]=i-l;
        if(s[i]-s[dq[inc]]>-eps)
            return 1;
    }
    return 0;
}

int main ()
{
    int i;
    double st,dr,m,sol;
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d%d%d",&n,&l,&u);
    for(i=1;i<=n;i++)
        scanf("%d",&v1[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&v2[i]);
    st=0.0;dr=1000.0;
    wh4ile(st+eps<dr)
    {
        m=(st+dr)*0.5;
        if(merge(m))
        {
            sol=m;
            st=m;
        }
        else
            dr=m;
    }
    printf("%.2lf\n",sol);
    return 0;
}