Cod sursa(job #1077152)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 10 ianuarie 2014 22:24:41
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <cstdio>
#include <algorithm>
#define Nmax 30005
#define eps 0.00001

using namespace std;

int N,L,U,v[Nmax],t[Nmax],poz[Nmax];
double s[Nmax],Q[Nmax];

inline bool Ok(double x)
{
    int i,st=1,dr=0;
    double maxim=-2000000000;
    s[0]=0;
    for(i=1;i<=N;++i)
        s[i]=s[i-1]+(1.0*v[i]-1.0*x*t[i]);

    for(i=L;i<=N;++i)
    {
        while(st<=dr && poz[st]<i-U)
            ++st;
        while(st<=dr && Q[dr]>s[i-L])
            --dr;
        ++dr;
        Q[dr]=s[i-L];
        poz[dr]=i-L;
        maxim=max(maxim,s[i]-s[poz[st]]);
    }
    return (maxim>=0);
}

int main()
{
    double st,dr,mij,sol;
    int i;
    freopen ("secv3.in","r",stdin);
    freopen ("secv3.out","w",stdout);
    scanf("%d%d%d", &N,&L,&U);
    for(i=1;i<=N;++i)
        scanf("%d", &v[i]);
    for(i=1;i<=N;++i)
        scanf("%d", &t[i]);

    st=0; dr=2000;
    while(st<dr+eps)
    {
        mij=(st+dr)/2;
        if(Ok(mij))
        {
            sol=mij;
            st=mij+eps;
        }
        else
            dr=mij-eps;
    }
    printf("%.2lf\n", sol);
}