Cod sursa(job #659562)

Utilizator vendettaSalajan Razvan vendetta Data 10 ianuarie 2012 18:54:33
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <iomanip>
#include <deque>
#define nmax 30002

using namespace std;

int n, L, U, a[nmax], b[nmax];
double v[nmax], s[nmax];
deque<int> dq;
double sol;

ifstream f("secv3.in");
ofstream g("secv3.out");

void citeste(){

    f>>n>>L>>U;
    for(int i=1; i<=n; ++i) f>>a[i];
    for(int i=1; i<=n; ++i) f>>b[i];

}

int rezolva(double x){

    dq.clear();

    for(int i=1; i<=n; ++i){
        s[i] = s[i-1] + a[i] - x*b[i];
    }

    for(int i=L; i<=n; ++i){
        while(!dq.empty() && s[i-L+1] <= s[ dq.back() ] ) dq.pop_back();
        dq.push_back(i-L);
        while ( i - U - 1 >= dq.front()) dq.pop_front();
        //d[i] = dq.front();
        if (s[i] - s[dq.front()] >= 0) return 1;
    }

    return 0;

}

void bs(){

    double st = 0;
    double dr = 10000000;

    while(dr - st > 0.0001){
        double mij = (st + dr) / 2;
        if (rezolva(mij)){
            sol = mij;
            st = mij+0.0001;
        }else dr = mij - 0.0001;
    }

    g<<setprecision(5)<<sol<<"\n";

}

int main(){

    citeste();
    bs();

    f.close();
    g.close();

    return 0;

}