Cod sursa(job #3141102)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 12 iulie 2023 12:08:41
Problema Secventa 3 Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;

int d[30001], t[30001];
deque <int> deq;
bool Deque(double k, int n, int p, int u){
    deq.clear();
    for(int i = p; i <= n; i++){
        if(!deq.empty() && deq.front() < i - u)
            deq.pop_front();
        while(!deq.empty() && 1.0 * d[deq.back()] - k * t[deq.back()] >= 1.0 * deq[i - p] - k * t[i - p])
            deq.pop_back();
        deq.push_back(i - p);
        if(1.0 * d[deq.front()] - k * t[deq.front()] < 1.0 * d[i] - k * t[i])
            return true;
    }
    return false;
}

int main() {
    int i, n, l, u, j;
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    scanf("%d%d%d", &n, &l ,&u);
    for(i = 1; i <= n; i++){
        scanf("%d", &d[i]);
        d[i] += d[i - 1];
    }
    for(i = 1; i <= n; i++){
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    double pas;
    double ans;
    for(ans = 0.0, pas = 1000.0, j = 0; j < 40; j++){
        if(Deque(ans + pas, n, l, u))
            ans += pas;
        pas /= 2.0;
    }
    deq.clear();
    printf("%.2lf", ans);

    return 0;
}