Cod sursa(job #184736)

Utilizator tm_raduToma Radu tm_radu Data 24 aprilie 2008 10:21:43
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <stdio.h>
#define NM 30001
#define lf (nod<<1)
#define rt (lf+1)
#define mij ((st+dr)>>1)
#define INF 200000000

int n, x, y;
int a[NM], b[NM];
int i, j, pos, lb, hb;
double k;
double s[NM], sm[3*NM], smax;

void Build(int nod, int st, int dr);
void Query(int nod, int st, int dr);
double Cbin(double st, double dr);
int Ok(double v);

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d %d %d", &n, &x, &y);
    for ( i = 1; i <= n; i++ )
        scanf("%d", &a[i]);
    for ( i = 1; i <= n; i++ )
        scanf("%d", &b[i]);
        
    printf("%.2lf\n", Cbin(0, INF));
    
    return 0;
}

void Build(int nod, int st, int dr)
{
    if ( st == dr )
    {
        sm[nod] = s[st];
        return;
    }
    Build(lf, st, mij);
    Build(rt, mij+1, dr);
    sm[nod] = sm[lf] > sm[rt] ? sm[rt] : sm[lf];
}

void Query(int nod, int st, int dr)
{
    if ( lb <= st && dr <= hb )
    {
        k = k > sm[nod] ? sm[nod] : k;
        return;
    }
    if ( lb <= mij ) Query(lf, st, mij);     
    if ( mij < hb ) Query(rt, mij+1, dr);
}

int Ok(double v)
{
    for ( i = 1; i <= n; i++ )
        s[i] = s[i-1] + (double)a[i] - v*(double)(b[i]);
    Build(1, 0, n);
    smax = -INF;
    for ( i = x; i <= n; i++ )
    {
        lb = i-y < 0 ? 0 : i-y;
        hb = i-x < 0 ? 0 : i-x;
        k = INF;
        Query(1, 0, n);
        if ( smax < s[i]-k ) smax = s[i]-k;
    }
    return smax < 0 ? 0 : 1;
}

double Cbin(double st, double dr)
{
    int niv = 0;
    while ( niv != 30 )
    {
        niv++;
        double mi = (st+dr)/2;
        if ( Ok(mi) ) st = mi;
        else          dr = mi;
    }
    return st;
}