Cod sursa(job #2811349)

Utilizator octavi26octavian octavi26 Data 1 decembrie 2021 21:22:54
Problema Secventa 3 Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>
#define N 791

using namespace std;

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

int n;
int l, r;
int a[N];
int b[N];

double error = 0.0001;

void Citire()
{
    int i;
    fin >> n >> l >> r;
    for( i=1; i<=n; i++ )
        fin >> a[i];
    for( i=1; i<=n; i++ )
        fin >> b[i];
}

double v[30005];
deque<int> d;

bool Verif( double x )
{
    int i;

    d.clear();
    for ( i=1; i<=n; i++ )
        v[i] = v[i - 1] + a[i] - x * b[i];

    for ( i=1; i<=n; i++ )
    {
        while (!d.empty() && i - d.front() + 1 > r)
            d.pop_front();

        while (!d.empty() && v[d.back()] >= v[i - l])
            d.pop_back();

        d.push_back(i - l);
        if (v[i] - v[d.front()] >= 0.0)
            return true;
    }
    return false;
}

void Rezolvcare()
{
    double st = 0.0, dr = 2000.0;
    double sol = 0;
    while (dr - st >= error)
    {
        double mid = (st + dr) / 2.0;
        if (Verif(mid))
        {
            sol = mid;
            st = mid;
        }
        else dr = mid;
    }
    fout << fixed << setprecision(2) << sol << '\n';
}

int main()
{
    Citire();
    Rezolvcare();
    fin.close();
    fout.close();
    return 0;
}