Cod sursa(job #3320192)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 4 noiembrie 2025 15:27:34
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

#define ld double

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

const int NMAX = 3e4;

int n, l, u;
int a[NMAX + 1];
int b[NMAX + 1];
int sp_a[NMAX + 1];
int sp_b[NMAX + 1];

ld get_value(int i, ld x) {
    return sp_a[i] - x * sp_b[i];
}

bool check(ld x) {
    deque<int> dq;
    for(int i = l; i <= n; i++) {
        while(!dq.empty() && dq.front() < i - u + 1) {
            dq.pop_front();
        }

        ld value_here = get_value(i - l, x);
        while(!dq.empty() && get_value(dq.back() - 1, x) >= value_here) {
            dq.pop_back();
        }
        dq.push_back(i - l + 1);

        if(get_value(i, x) >= get_value(dq.front() - 1, x)) {
            return true;
        }
    }
    return false;
}

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

    for(int i = 1; i <= n; i++) {
        sp_a[i] = sp_a[i - 1] + a[i];
        sp_b[i] = sp_b[i - 1] + b[i];
    }

    ld left = 0, right = 1e9;
    int iter = 100;
    while(iter--) {
        ld mid = (left + right) / 2;
        if(check(mid)) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    fout << fixed << setprecision(2) << left << '\n';
    return 0;
}