Cod sursa(job #3315110)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 12 octombrie 2025 14:28:37
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

const int N=3e4+5;

int n,l,u,c[N], t[N];

double v[N], eps=1e-3;

bool check(double x){
    for (int i=1;i<=n;i++){
        v[i]=v[i-1]+c[i]*1.0-x*t[i];
    }
    deque<int>q;
    for (int i=0;i<=u-l;i++){
        while (!q.empty() && v[q.back()]>v[i]){
            q.pop_back();
        }
        q.push_back(i);
    }
    for (int i=u;i<=n;i++){
        while (!q.empty() && q.front()<i-u){
            q.pop_front();
        }
        while (!q.empty() && v[q.back()]>v[i-l]){
            q.pop_back();
        }
        q.push_back(i-l);
        if (v[i]-v[q.front()]>=eps)return true;
    }
    return false;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>l>>u;
    for (int i=1;i<=n;i++){
       cin>>c[i];
    }
    for (int i=1;i<=n;i++){
        cin>>t[i];
    }
    double left=0, right=1005,ans=0;
    while (right-left>=eps){
        double mid=(left+right)/2;
        if (check(mid)){
            ans=mid;
            left=mid;
        }
        else{
            right=mid;
        }
    }
    cout<<fixed<<setprecision(2)<<ans;
    return 0;
}