Cod sursa(job #3161048)

Utilizator AswVwsACamburu Luca AswVwsA Data 25 octombrie 2023 16:58:09
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
//oftica si durere in suflet
#include <fstream>
#include <climits>
#include <deque>
#include <cfloat>
#define ll long long

using namespace std;

const int NMAX = 30000;
const int BULAN = 30;
const double EPS = 0.00001;
//0.832513
//0.833292


int s1[NMAX + 1];
int s2[NMAX + 1];

int n, l, u;

double s3[NMAX + 1]; //s1(i) - s2(i) * val


bool ok(double val) //daca exista secventa care sa aiba valoarea aia >= val
{
    int i;
    for (i = 1; i <= n; i++)
    {
        s3[i] = s1[i] - s2[i] * val;
    }
    deque <int> d;
    for (i = 1; i <= n; i++)
    {
        while (!d.empty() and d.front() < i - u)
            d.pop_front();
        if (i - l >= 1)
        {
            while (!d.empty() and s3[d.back()] > s3[i - l])
                d.pop_back();
            d.push_back(i - l);
        }
        if (!d.empty())
        {
            if (s3[i] >= s3[d.front()])
                return true;
        }
    }
    return false;
}

signed main()
{
    ifstream cin("secv3.in");
    ofstream cout("secv3.out");
    int i;
    cin >> n >> l >> u;
    for (i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        s1[i] = s1[i - 1] + x;
    }
    for (i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        s2[i] = s2[i - 1] + x;
    }
    double med, st = 0, dr = 1000;
    double sol = -1;
    for (i = 1; i <= BULAN and (st <= dr); i++)
    {
        med = ((st + dr) / 2);
        if (ok(med))
        {
            sol = med;
            st = med + EPS;
        }
        else
            dr = med - EPS;
    }
    cout << sol;
}