Cod sursa(job #2569047)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 4 martie 2020 10:54:08
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <iomanip>

using namespace std;

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

const int N_MAX = 3e4;
const double DIF = 0.0001;

deque<pair<double, int>> dq;
int n, l, u;
int c[N_MAX + 10], t[N_MAX + 10];

void scan()
{
    in >> n >> l >> u;

    for(int i = 1; i <= n; i++)
    {
        int x;
        in >> x;

        c[i] = c[i-1] + x;
    }

    for(int i = 1; i <= n; i++)
    {
        int x;
        in >> x;

        t[i] = t[i-1] + x;
    }
}

bool check(double val)
{
    double v[N_MAX + 10];

    for(int i = 1; i <= n; i++)
        v[i] = c[i] - t[i] * val;

    dq.clear();

    for(int i = 1; i < n; i++)
    {
        while(!dq.empty() && dq.back().first >= v[i])
            dq.pop_back();

        dq.emplace_back(v[i], i);

        if(i - u >= dq.front().second)
            dq.pop_front();

        if(i >= l && v[i+1] - dq.front().first > 0)
            return 1;
    }

    return 0;
}

int main()
{
    scan();

    double st = 0.0, dr = 1000.0, mid;

    while(dr - st >= DIF)
    {
        mid = (st + dr) / 2.0;

        if(check(mid))
            st = mid;
        else
            dr = mid;
    }

    out << fixed << setprecision(2) << mid << '\n';

    return 0;
}