Cod sursa(job #3316946)

Utilizator magnifica5Tabarca Ioana magnifica5 Data 21 octombrie 2025 14:52:36
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
int scost[30001], stimp[30001];
int n, l, u, c, t;
bool ordine(double x, int i, int j){
    return scost[i] - x * stimp[i] < scost[j] - stimp[j] * x;
}
bool verif(double x){
    deque<int> dq;
    for(int i = 1; i <= n; i ++){
        if(i > u){
            if(!dq.empty() && dq.front() < i - u){
                dq.pop_front();
            }
        }
        if(i > l){
            while(!dq.empty() && ordine(x, i - l, dq.back())){
                dq.pop_back();
            }
            dq.push_back(i - l);
        }
        if(!dq.empty() && !ordine(x, i, dq.front())){
            return 1;
        }
    }
    return 0;
}
int main()
{
    cin >> n >> l >> u;
    for(int i = 1; i <= n; i ++){
        cin >> c;
        scost[i] = scost[i - 1] + c;
    }
    for(int i = 1; i <= n; i ++){
        cin >> t;
        stimp[i] = stimp[i - 1] + t;
    }
    double st = 0, dr = 1000, x, sol;
    for(int i = 1; i <= 100; i ++){
        x = (st + dr) / 2;
        if(verif(x)){
            st = x;
            sol = x;
        }
        else{
            dr = x;
        }
    }
    cout << fixed << setprecision(2) << sol;
}