Cod sursa(job #3356181)

Utilizator rares89_Dumitriu Rares rares89_ Data 30 mai 2026 02:23:38
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

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

int N, L, U;
double C[30005], T[30005], S[30005];
int dq[30005];

bool check(double X) {
    for (int i = 1; i <= N; ++i) {
        S[i] = S[i - 1] + C[i] - X * T[i];
    }
    
    int st = 1, dr = 0;
    for (int i = L; i <= N; ++i) {
        int j = i - L;
        
        while (st <= dr && S[dq[dr]] >= S[j]) {
            dr--;
        }
        
        dq[++dr] = j;
        
        while (st <= dr && dq[st] < i - U) {
            st++;
        }
        
        if (S[i] - S[dq[st]] >= 0.0) {
            return true;
        }
    }
    
    return false;
}

int main() {
    fin >> N >> L >> U;
    for (int i = 1; i <= N; ++i) fin >> C[i];
    for (int i = 1; i <= N; ++i) fin >> T[i];
    
    double left = 0.0, right = 1000.0, ans = 0.0;
    
    for (int step = 0; step < 60; ++step) {
        double mid = (left + right) / 2.0;
        if (check(mid)) {
            ans = mid;
            left = mid;
        } else {
            right = mid;
        }
    }
    
    fout << fixed << setprecision(2) << ans << "\n";
    
    fin.close();
    return 0;
}