Cod sursa(job #1691138)

Utilizator Daria09Florea Daria Daria09 Data 16 aprilie 2016 22:35:29
Problema Secventa 3 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#define NMAX 3005
#define eps 0.00001
#include <cstdio>
using namespace std;
ifstream f("secv3.in");
int n,l,u,v[NMAX],t[NMAX],poz[NMAX];
double s[NMAX],Q[NMAX];
bool okay(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);
}
void solve()
{
    double st,dr,mij,sol=0; int i;
    f>>n>>l>>u;
    for(i=1;i<=n;i++)f>>v[i];
    for(i=1;i<=n;i++)f>>t[i];
    st=0; dr=2000;
    while(st<dr+eps)
    {
        mij=(st+dr)/2;
        if(okay(mij))
        {
            sol=mij;
            st=mij+eps;
        }
        else
            dr=mij-eps;
    }
    freopen("secv3.out","w",stdout);
    printf("%.2lf\n", sol);
}
int main()
{
    solve();
    return 0;
}