Cod sursa(job #2933456)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 5 noiembrie 2022 10:58:05
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
deque<int> q;
int n, l, u, a[30001], b[30001];
float ls, ld, mij, sum, c[30001], minim[30001];
int solve(float k)
{
    c[0] = 0;
    deque<int> d;
    for(int i = 1; i <= n; ++ i)
        c[i] = c[i - 1] + (a[i] - k * b[i]);
    d.push_back(0);
    minim[0] = 0;
    for(int i = 1; i <= n; ++ i)
    {
        while(!d.empty() && c[i] <= c[d.back()])
            d.pop_back();
        d.push_back(i);
        if(i - d.front() == u - l + 1)
            d.pop_front();
        minim[i] = c[d.front()];
    }
    for(int i = l; i <= n; ++ i)
    {
        if(c[i] - minim[i - l] >= 0)
            return 1;
    }
    return 0;
}
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];
    }
    ls = 0.001;
    ld = 1000;
    for(int i = 1; i <= 40; ++ i)
    {
        mij = (ls + ld) / 2;
        if(solve(mij) == 1)
            ls = mij;
        else
            ld = mij;
    }
    fout << fixed << setprecision(3) << ls;
    return 0;
}