Cod sursa(job #3315150)

Utilizator horatiu.avramAvram Popa Cristian Horatiu horatiu.avram Data 12 octombrie 2025 16:37:20
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4;
const double eps=0.00001;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int n,l,u;
double c[MAXN+1],t[MAXN+1];
bool check(double x) {
    vector<double>pfx(n+1,0);
    for(int i=1; i<=n; i++) {
        pfx[i]=pfx[i-1]+c[i]-x*t[i];
    }
    deque<int>dq;
    double res=0;
    for(int i=l; i<=n; i++) {
        while(!dq.empty()&&pfx[dq.back()]>=pfx[i-l+1]) {
            dq.pop_back();
        }
        dq.push_back(i-l);
        if(!dq.empty()) {
            res=max(res,pfx[i]-pfx[dq.front()]);
        }
        if(!dq.empty()&&dq.front()<i-u) {
            dq.pop_front();
        }
    }
    return res>0;
}
int main() {
    fin>>n>>l>>u;
    for(int i=1; i<=n; i++) {
        fin>>c[i];
    }
    for(int i=1; i<=n; i++) {
        fin>>t[i];
    }
    double l=0,r=1e9;
    while(r-l>=eps) {
        double mid=(l+r)/2;
        if(check(mid)) {
            l=mid;
        } else {
            r=mid;
        }
    }
    fout<<fixed<<setprecision(2)<<l;
    return 0;
}