Cod sursa(job #1218018)

Utilizator mihaimusatMihai Musat mihaimusat Data 9 august 2014 10:06:25
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <cstdio>

using namespace std;

const int Nmax=30005;

int A[Nmax], B[Nmax], Dq[Nmax];
double S[Nmax];
int N, L, U;

bool check(double t)
{
    for(int i=1;i<=N;i++)
        S[i]=S[i-1]+A[i]-B[i]*t;

    int st=1, dr=0;
    for(int i=L;i<=N;i++)
    {
        for(;st<=dr&&Dq[st]+U<i;st++);
        for(;st<=dr&&S[i-L]<=S[Dq[dr]];dr--);

        Dq[++dr]=i-L;

        if(S[i]-S[Dq[st]]>=0) return 1;
    }

    return 0;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);

    scanf("%d%d%d", &N, &L, &U);

    for(int i=1;i<=N;i++) scanf("%d", &A[i]);
    for(int i=1;i<=N;i++) scanf("%d", &B[i]);

    int Sol, step;
    for(Sol=0, step=(1<<17);step;step>>=1)
    {
        if(check((double)(Sol|step)/100))
            Sol|=step;
    }

    printf("%.2lf\n", (double)Sol/100);
}