Cod sursa(job #2922110)

Utilizator ciacliboiiiciacli stefan ciacliboiii Data 4 septembrie 2022 09:19:06
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 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];
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(c[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 + 1)
            d.pop_front();
        if(i >= l)
        {
            sum = 0;
            sum = c[i] - c[d.front()];
            if(sum >= 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;
}