Cod sursa(job #119886)

Utilizator sealTudose Vlad seal Data 3 ianuarie 2008 16:42:18
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define Nm (1<<15)
#define Vm 3000000000u
int A[Nm],B[Nm],Dp[Nm],n,a,b;
long long S[Nm],Dv[Nm];

void read()
{
    int i;

    freopen("secv3.in","r",stdin);
    scanf("%d%d%d",&n,&a,&b);
    for(i=1;i<=n;++i)
        scanf("%d",A+i);
    for(i=1;i<=n;++i)
        scanf("%d",B+i);
}

int ok(unsigned m)
{
    int l=0,r=-1,i,k=b-a+1;

    S[0]=0;
    for(i=1;i<=n;++i)
        S[i]=S[i-1]+A[i]*100-B[i]*m;

    for(i=0;i<=n-a;++i)
    {
        while(l<=r && S[i]<Dv[r])
            --r;
        Dv[++r]=S[i];
        Dp[r]=i;
        if(Dp[l]==i-k)
            ++l;
        if(S[i+a]>=Dv[l])
            return 1;
    }
    return 0;
}

unsigned solve()
{
    unsigned l,r,m;

    l=0; r=Vm;
    while(l<r)
    {
        m=l+r+1>>1;
        if(ok(m))
            l=m;
        else
            r=m-1;
    }
    return l;
}

void write(unsigned ans)
{
    freopen("secv3.out","w",stdout);
    printf("%.2f\n",ans/(float)100);
}

int main()
{
    read();
    write(solve());
    return 0;
}