Cod sursa(job #3366972)

Utilizator Andreea3425Diaconu Andreea Andreea3425 Data 5 octombrie 2026 15:42:14
Problema Secventa 3 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;

#define N 30000
#define X 1000

int a[N+1], b[N+1];
double c[N+1];

bool ok(double mij, int n, int l, int u){
    int i;

    for (i=0; i<n; i++)
        c[i]=(double)a[i]-mij*b[i];

    deque <int> q;

    for (i=0; i<n; i++){
        while (!q.empty() && c[i]<c[q.back()])
            q.pop_back();

        q.push_back(i);

        if (c[q.front()]<=c[i])
            return 1;

        while (!q.empty() && q.front()<=l-u+1)
            q.pop_front();
    }

    return 0;
}

int main()
{
    int n,l,u,i;
    double st,dr,mij;

    cin >> n >> l >> u;

    for (i=0; i<n; i++){
        cin >> a[i];
        a[i]+=a[i-1];
    }

    for (i=0; i<n; i++){
        cin >> b[i];
        b[i]+=b[i-1];
    }

    st=0;
    dr=N*X;
    while (dr-st>0.01){
        mij=(st+dr)/2;
        if (ok(mij, n, l, u)==0)
            st=mij+1;
        else
            dr=mij-1;
    }

    cout << fixed << setprecision(2) << st-1 << '\n';

    return 0;
}