Cod sursa(job #3140032)

Utilizator not_anduAndu Scheusan not_andu Data 3 iulie 2023 16:30:13
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <deque>

using namespace std;

#define INFILE "secv3.in"
#define OUTFILE "secv3.out"
#define VMAX 30002
#define LIMITA 1e-10

ifstream fin (INFILE);
ofstream fout (OUTFILE);

int n, l, u;
double a[VMAX], b[VMAX], v[VMAX];

bool verif(double nr){

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

    deque<int> dq;

    double sumaMax = -1;

    for(int i = l; i <= n; ++i){

        while(!dq.empty() && dq.front() < i - u){
            dq.pop_front();
        }

        while(!dq.empty() && v[dq.back()] >= v[i - l]){
            dq.pop_back();
        }

        dq.push_back(i - l);

        sumaMax = max(v[i] - v[dq.front()], sumaMax);

    }

    return sumaMax >= 0;

}

void cautareBinara(){

    double st = 0, dr = 2 * VMAX;

    while(dr - st >= LIMITA){

        double mij = (st + dr) / 2;

        if(verif(mij)){
            st = mij;
        }
        else{
            dr = mij;
        }

    }

    fout << st << '\n';

}

void solve(){

    fin >> n >> l >> u;

    for(int i = 1; i <= n; ++i){
        fin >> a[i];
    }

    for(int i = 1; i <= n; ++i){
        fin >> b[i];
    }

    cautareBinara();

}

int main(){
    solve();
    return 0;
}