Cod sursa(job #3229597)

Utilizator Dani111Gheorghe Daniel Dani111 Data 16 mai 2024 19:41:36
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;

const int MAX = 30000;
int N, L, U;
int C[MAX + 3], T[MAX + 3];
double V[MAX + 3];

double bs(double X) {
    deque<int>dq;
    for(int i = 1; i <= N; i++) {
        V[i] = C[i] - X * T[i]; 
    }   

    // for(int i = 1; i <= N; i++) {
    //     cout << V[i] << ' ';
    // }
    // cout << '\n';

    double ans = -INT_MAX;
    int ri = 0;
    for(int i = 1; i <= N; i++) {
        while(ri < i - L) {
            ri++;   
            while(!dq.empty() && V[dq.front()] > V[ri]) dq.pop_front();
            dq.push_front(ri);
        }

        while(!dq.empty() && dq.back() <= i - U) dq.pop_back();

        if(!dq.empty())
        ans = max(ans, V[i] - V[dq.back()]);
    }
    //cout << ans << '\n';
    return ans;
}   

int main() {
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);

    cin >> N >> L >> U;

    for(int i = 1; i <= N; i++) {
        cin >> C[i];
        C[i] += C[i - 1];
    }

    for(int i = 1; i <= N; i++) {
        cin >> T[i];
        T[i] += T[i - 1];
    }

    double st = 0, dr = MAX;
    double best = 0;

    for(int i = 0; i <= 200; i++) {
        //cout << st << ' ' << dr << '\n';
        double mid = (st + dr) / 2;
        if(bs(mid) >= 0) st = mid, best = max(best, mid);
        else dr = mid;
    }

    cout << fixed << setprecision(2) << best;
}

/*

    C / T = X (X maxim)


    C[l] + C[l + 1] ... + C[r] = X * T[l] + X * T[l + 1] + ... X * T[r]


    C[l] + C[l + 1] + ... + C[r] - X * T[l] - X * T[l + 1] - ... - X * T[r] >= 0


*/