Cod sursa(job #2809976)

Utilizator BorodiBorodi Bogdan Borodi Data 28 noiembrie 2021 00:20:31
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
	
#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
#define pb push_back
 
const string filename = "secv3";
 
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");
 
const double err = 0.0001;
 
int n, l, r;
int a[30005], b[30005];
double c[30005];
deque<int> d;
 
bool ok(double x)
{
    d.clear();
    for (int i = 1; i <= n; ++i)
        c[i] = c[i - 1] + a[i] - x * b[i];
    for (int i = l; i <= n; ++i)
    {
        if(!d.empty() && i - d.front() + 1 > r)
            d.pop_front();
        while (!d.empty() && c[d.back()] >= c[i - l])
            d.pop_back();
        d.push_back(i - l);
        if (c[i] - c[d.front()] >= 0.0)
            return true;
    }
    return false;
}
 
int main() {
 
    fin >> n >> l >> r;
    for (int i = 1; i <= n; ++i)
        fin >> a[i];
    for (int i = 1; i <= n; ++i)
        fin >> b[i];
 
    double st = 0.0, dr = 2000.0, ans = 0;
    while (dr - st >= err)
    {
        double mid = (st + dr) / 2.0;
        if (ok(mid)) {
            ans = mid;
            st = mid;
        }
        else dr = mid;
    }
    fout << fixed << setprecision(2) << ans << '\n';
    fin.close();
    fout.close();
    return 0;
}