Cod sursa(job #3315382)

Utilizator ZebraMorariu Radu Dimitri Zebra Data 14 octombrie 2025 06:12:49
Problema Secventa 3 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 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;
double c[Nmax], t[Nmax], prefix[Nmax];

bool verif(double k)
{
    prefix[0] = 0;
    for (int i = 1; i <= n; ++i)
        prefix[i] = prefix[i - 1] + c[i] - k * t[i];

    deque<int> dq;
    double rez = 0;
    for (int i = L; i <= n; ++i)
    {
        while (!dq.empty() && prefix[dq.back()] >= prefix[i - L + 1])
            dq.pop_back();

        dq.push_back(i - L);

        if (!dq.empty())
            rez = max(rez, prefix[i] - prefix[dq.front()]);

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

    return (rez > 0);
}

int main()
{
    fin >> n >> L >> U;
    for (int i = 1; i <= n; ++i) fin >> c[i];
    for (int i = 1; i <= n; ++i) fin >> t[i];

    double st = 0, dr = n, best = 0;
    for(int it = 0; it < 60; ++it)
    {
        double mij = (st + dr) / 2;
        if (verif(mij)){
            best = mij;
            st = mij;
        }
        else
            dr = mij;
    }

    fout << fixed << setprecision(2) << st;
    return 0;
}