Cod sursa(job #2262799)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 17 octombrie 2018 20:19:44
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>

#define NM 30002

using namespace std;

int n, l, u;

double a[NM], b[NM];
double mx = -1;
double sp[NM];

multiset <double> s;

bool f(double cf)
{
    s.clear();
    for(int i = 1; i <= n; i++)
        sp[i] = sp[i - 1] + a[i] - (b[i] * cf);
    for(int i = l; i <= n; i++)
    {
        s.insert(sp[i - l]);
        if(i - u >= 0)
        {
            auto it = s.find(sp[i - u]);
            s.erase(it);
        }
        auto it = s.upper_bound(sp[i]);
        if(it != s.begin())
            return 1;
    }
    return 0;
}

int main()
{
    ifstream fin ("secv3.in");
    ofstream fout ("secv3.out");
    fin >> n >> l >> u;
    for(int i = 1; i <= n; i++)
        fin >> a[i];
    for(int i = 1; i <= n; i++)
        fin >> b[i];
    for(int i = 1; i <= n; i++)
        if(a[i] / b[i] > mx)
            mx = a[i] / b[i];
    double l = 0, r = mx, mid;
    while(r - l > 0.001)
    {
        mid = (l + r) / 2;
        if(f(mid) == 0)
            r = mid - 0.001;
        else
            l = mid;
    }
    fout << fixed << setprecision(2) << l << "\n";
    return 0;
}