Cod sursa(job #3363273)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 14 august 2026 22:18:27
Problema Secventa 3 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
typedef long double ld;
int n, L, R, cost[30003], timp[30003];
ld v[30003], sp[30003];

inline int check(ld x) {
    for(int i=1; i<=n; i++) {
        v[i] = cost[i] - x * timp[i];
        sp[i] = sp[i - 1] + v[i];
    }
    ///aflu subsecv de suma maxima cu lung in [L, R]
    deque<int> dq;
    ld sumMax = -10000.0;
    for(int i=L; i<=n; i++) {
        while(!dq.empty() && sp[i] - sp[i - L] >= sp[i] - sp[i - dq.back()]) dq.pop_back();
        if(!dq.empty() && i - dq.front() >= R) dq.pop_front();
        dq.push_back(i - L);
        sumMax = max(sumMax, sp[i] - sp[dq.front()]);
    }
    return sumMax >= 0.0;
}

int main()
{
    fin >> n >> L >> R;
    for(int i=1; i<=n; i++) fin >> cost[i];
    for(int i=1; i<=n; i++) fin >> timp[i];
    ld st = 1e-5, dr = 10000, sol;
    for(int pas=1; pas<=100; pas++) {
        ld mid = (st + dr) / 2.0;
        if(check(mid)) sol = mid, st = mid;
        else dr = mid;
    }
    fout << fixed << setprecision(6) << sol;

    return 0;
}