Cod sursa(job #2668807)

Utilizator Tudor_PascaTudor Pasca Tudor_Pasca Data 5 noiembrie 2020 14:47:47
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.49 kb
#include<iostream>
#include<fstream>
#include<deque>
#include<iomanip>

using namespace std;

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

const double DIF = 0.0001;
int n, l, u;
double st = 0.0, dr = 1000.0;
int c[30100], t[30100];
double v[30100];

bool check(double value)
{
   //cout << "MID: " << value << '\n';

    for(int i = 1; i <= n; i++)
    {
        v[i] = c[i] - t[i] * value;
        //cout << v[i] << ' ';
    }

    //cout << "\n";

    deque<pair<double, int>> dq;

    dq.emplace_back(0, 0);

    for(int i = 1; i <= n; i++)
    {
        //cout << i << ' ' << dq.front().second << ' ' << v[i] - dq.front().first << '\n';

        if(v[i] - dq.front().first >= 0.0)
            return 1;

        while(!dq.empty() && v[i] < dq.back().first)
            dq.pop_back();

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

        if(dq.front().second < i - u)
            dq.pop_front();
    }

    return 0;
}

int main()
{
    in >> n >> l >> u;

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

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

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

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

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

        //cout << mid << ' ' << check(mid) << '\n';

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

    out << setprecision(2) << st << '\n';

    return 0;
}