Cod sursa(job #3311787)

Utilizator eric.mesterEric Mestereaga eric.mester Data 24 septembrie 2025 11:39:57
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <bits/stdc++.h>
#define NMAX 30002

using namespace std;

ifstream fin("secv3.in");
ofstream fout("secv3.out");

int N,L,U;
int S[NMAX],T[NMAX];

bool is_better(double x)
{
    deque <int> dq;
    for(int i=L;i<=N;i++){
        int j = i-L + 1;
        while(!dq.empty() && T[dq.back()-1] - x*S[dq.back() - 1] <= T[j-1] - x * S[j-1]){
            dq.pop_back();
        }
        dq.push_back(j);
        while(dq.front() <= i-U+1){
            dq.pop_front();
        }
        j = dq.front();
        if(T[i] - x*S[i] > T[j-1] - x*S[j-1]){
//            cout << j << " , " << i << "\n";
            return true;
        }
    }
    return false;
}

double caut_bin()
{
    double ret = 0;
    double left = 0;
    double right = 1002;
    int it = 60;
    while(it--){
        double mid = (left + right)/2.;
        if(is_better(mid)){
            ret = mid;
            left = mid;
        }else{
            right = mid;
        }
    }
    return ret;
}

int main()
{
    fin >> N >> L >> U;
    for(int i=1;i<=N;i++){
        fin >> T[i];
        T[i]+=T[i-1];
    }
    for(int i=1;i<=N;i++){
        fin >> S[i];
        S[i]+=S[i-1];
    }
//    cout << is_better(1) << "\n";
    fout << fixed << setprecision(2)<< caut_bin();
}