Cod sursa(job #1254970)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 3 noiembrie 2014 20:48:21
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <iomanip>
#include <deque>

#define NMAX 30005
#define VALMAX 1005
using namespace std;

int n,u,l;
int c[NMAX];
int t[NMAX];

deque<int> coada;
double v[NMAX];

bool ok(double m){
    int i;
    for(i=1;i<=n;i++){
        v[i]=c[i]-m*t[i];
        v[i]+=v[i-1];
    }

    coada.clear();
    for(i=l;i<=n;i++){
        while(!coada.empty() && i-coada.front()>u)
            coada.pop_front();
        while(!coada.empty() && v[i-l]<=v[coada.back()])
            coada.pop_back();

        coada.push_back(i-l);

        if(v[coada.front()]<=v[i])
            return 1;
    }

    return 0;
}

int main()
{
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");

    cin>>n>>l>>u;

    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=n;i++)
        cin>>t[i];

    double st=0;
    double dr=VALMAX;
    double mijl=dr/2;
    double ans=0;

    for(int steps=0;steps<20;steps++){
        if(ok(mijl)){
            st=mijl;
            ans=mijl;
        }
        else
            dr=mijl;

        mijl=(st+dr)*0.5;
    }

    cout<<fixed<<setprecision(6)<<ans<<'\n';

    cin.close();
    cout.close();
    return 0;
}