Cod sursa(job #3308554)

Utilizator iustinola16Olariu Iustin iustinola16 Data 26 august 2025 09:59:09
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

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

const int NMAX = 3e4 + 5;

int N, L, U;
int C[NMAX], T[NMAX];
double V[NMAX];

double check(double X)
{
    for (int i = 1; i <= N; i++) {
        V[i] = C[i] - X * T[i];
    }

    deque<int> dq;
    double maxim = -1e9;
    for (int i = L; i <= N; i++) {
        int j = i - L;

        while (!dq.empty() && V[dq.back()] >= V[j]) {
            dq.pop_back();
        }

        dq.push_back(j);

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

        if (!dq.empty()) maxim = max(maxim, V[i] - V[dq.front()]);
    }

    return maxim;
}

int main()
{
    fin >> N >> L >> U;

    for (int i = 1; i <= N; i++) {
        fin >> C[i];
        C[i] += C[i - 1];
    }

    for (int i = 1; i <= N; i++) {
        fin >> T[i];
        T[i] += T[i - 1];
    }

    double st = 0, dr = 1000, ans = 0;
    while (dr - st >= 0.01) {
        double mid = (st + dr) / 2;
        if (check(mid) >= 0) {
            st = mid;
            ans = max(ans, mid);
        } else {
            dr = mid;
        }
    }

    fout << setprecision(2) << fixed << ans << "\n";
    return 0;
}