Cod sursa(job #733755)

Utilizator elfusFlorin Chirica elfus Data 12 aprilie 2012 21:41:28
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
//Sursa luata de la prietena mea Malina, nu-i asa ca e o fata pe cinste? :P

#include <stdio.h>
#include <string.h>
#define LMAX 30100

int N, P, q;
int A[LMAX], B[LMAX], Q[LMAX];
double sum[LMAX];

bool possible (double val)
{
    int i, p, u;
    double best = -1, now;

    memset (Q, 0, sizeof (Q));

    sum[0] = 0; p = u = 1;
    for (i = 1; i <= N; i ++)
        sum[i] = sum[i - 1] + A[i] - val * B[i];

    for (i = P; i <= N; i ++)
    {
        now = sum[i] - sum[Q[p]];
        if (now > best)
            best = now;
        while (p <= u && sum[Q[u]] >= sum[i - P + 1])
            u --;
        Q[++ u] = i - P + 1;
        if (Q[p] + q == i)
            p ++;
    }

    return best > 0;
}

double binary_search ()
{
    int left = 1, right = (1 << 30);
    double med, last;

    while (left <= right)
    {
        med = (double)(left + right) / 200.0;
        if (possible (med))
            left = (left + right) / 2 + 1, last = med;
        else
            right = (left + right) / 2 - 1;
    }

    return last;
}

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

    scanf ("%d%d%d", &N, &P, &q);

    int i;

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

    printf ("%.2lf", binary_search ());
    return 0;
}