Cod sursa(job #2917279)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 4 august 2022 10:24:55
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
/// Preset de infoarena
#include <fstream>
#include <iostream>
#include <deque>
#include <iomanip>

using namespace std;

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

const int maxN = 30005;
const double eps = 1e-3;
int n, l, u;
int c[maxN], t[maxN];
double v[maxN];
deque <int> dq;

bool check(double val)
{
    dq.clear();
    v[0] = 0;
    for(int i = 1; i <= n; i++)
    {
        v[i] = v[i - 1] + c[i] - val * t[i];
        if(i >= l)
        {
            while(!dq.empty() && v[i - l] <= v[dq.back()])
                dq.pop_back();
            dq.push_back(i - l);
            if(dq.front() == i - u)
                dq.pop_front();
            if(v[i] - v[dq.front()] >= 0)
                return 1;
        }
    }
    return 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 = 30000000, ans = 0;
    while(st + eps <= dr)
    {
        double med = (st + dr) / 2;
        if(check(med))
        {
            ans = med;
            st = med;
        }
        else
            dr = med;
    }
    fout << fixed << setprecision(3) << ans;
    return 0;
}