Cod sursa(job #3315380)

Utilizator ZebraMorariu Radu Dimitri Zebra Data 14 octombrie 2025 06:06:12
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)
{
    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])
            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 = 1, dr = n, best = 0;
    for(int i = 1; i <= 100; ++i)
    {
        double mij = (st + dr) / 2;
        if(verif(mij)){
            best = mij;
            st = mij + 1;
        }
        else
            dr = mij - 1;
    }

    fout << fixed << setprecision(2) << best;

    return 0;
}