Cod sursa(job #3321673)

Utilizator postolacheepostolache postolachee Data 10 noiembrie 2025 22:23:55
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 kb
/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize ("O3")
#define pb push_back
using namespace std;

int n, l, u;
long double c[30009], t[30009], pref[30009];

bool ook(long double x){
    pref[0] = 0.0L;
    for(int i=1;i <= n;i++)pref[i] = pref[i - 1] + c[i] - x * t[i];
    
    deque<int> dq;
    for(int i=l;i <= n;i++){
        int id = i - l;
        while(!dq.empty() && pref[id] <= pref[dq.back()])dq.pop_back();
        dq.pb(id);
        
        int lb = i - u;
        if(lb < 0)lb = 0;
        while(!dq.empty() && dq.front() < lb)dq.pop_front();
        
        if(!dq.empty() && pref[i] - pref[dq.front()] >= 0.0L)return true;
    }
    return false;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ifstream cin ("secv3.in");
    ofstream cout ("secv3.out");
    
    cin >> n >> l >> u;
    for(int i=1;i <= n;i++)cin >> c[i];
    for(int i=1;i <= n;i++)cin >> t[i];
    
    long double ll = 0.0L, rr = 1000.0L;
    for(int sigma=0;sigma < 67 * 2;sigma++){
        long double mid = (ll + rr) / 2.0L;
        if(ook(mid))ll = mid;
         else rr = mid;
    }
    
    cout << fixed << setprecision(2) << (double)ll << "\n";
    return 0;
}