Cod sursa(job #2683239)

Utilizator FrostfireMagirescu Tudor Frostfire Data 10 decembrie 2020 18:30:39
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>
#define eps 0.01
#define NMAX 30000

using namespace std;

ifstream f("secv3.in");
ofstream g("secv3.out");

int n, l, r;
double sp[NMAX+10], a[NMAX+10];
pair <double, double> v[NMAX+10];
deque <int> dq;

bool isOK(double val)
{   while(!dq.empty()) dq.pop_back();
    for(int i=1; i<=n; i++)
        {   a[i] = v[i].first - val * v[i].second;
            sp[i] = sp[i-1] + a[i];
            while(!dq.empty() && dq.front() < i - r) dq.pop_front();
            if(i >= l)
                {   while(!dq.empty() && sp[dq.back()] > sp[i-l]) dq.pop_back();
                    dq.push_back(i-l);
                    if(sp[i] - sp[dq.front()] >= 0) return 1;
                }
        }
    return 0;
}

int main()
{
    f >> n >> l >> r;
    for(int i=1; i<=n; i++) f >> v[i].first;
    for(int i=1; i<=n; i++) f >> v[i].second;
    double st = 0, dr = 1000, ans = 0;
    while(dr - st > eps)
        {   double mij = (st + dr) / 2;
            if(isOK(mij)) ans = mij, st = mij;
            else dr = mij;
        }
    g << setprecision(2) << fixed << ans << '\n';
    return 0;
}