Cod sursa(job #988789)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 23 august 2013 21:14:50
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#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;
}