Cod sursa(job #2786127)

Utilizator AlexNicuNicu Alexandru AlexNicu Data 20 octombrie 2021 12:29:51
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <deque>

using namespace std;

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

#define NMAX 30001
#define EPS 1e-5

int v[NMAX], coef[NMAX];
double sum[NMAX];
int stanga, dreapta, n;

bool verif(double val) {
    int i;
    for ( i = 1; i <= n; i++ ) {
        sum[i] = sum[i - 1] + v[i] - val * coef[i];
    }
    deque<int> q;
    for( i = stanga; i <= n; i++ ){
        while( !q.empty() && sum[i - stanga] <= sum[q.back()]){
            q.pop_back();
        }
        q.push_back(i - stanga);
        if( i - q.front() == dreapta ){
            q.pop_front();
        }
        if( sum[i] - sum[q.front()] >= 0.0 ){
            return 1;
        }
    }
    return 0;
}



int main() {
    int i;
    double st, dr, mid, ans;
    cin >> n >> stanga >> dreapta;
    for ( i = 1; i <= n; i++ ) {
        cin >> v[i];
    }
    for ( i = 1; i <= n; i++ ) {
        cin >> coef[i];
    }
    st = 0.0;
    dr = 1000.0;
    while ( dr - st >= EPS ) {
        mid = ( st + dr ) / 2;
        if ( verif(mid) ) {
            ans = mid;
            st = mid + EPS;
        }
        else {
            dr = mid - EPS;
        }
    }
    cout << ans;
    return 0;
}