Cod sursa(job #2761511)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 2 iulie 2021 15:15:25
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
#define EPS 1e-2

using namespace std;

const int NMAX = 30003;

int n, l, u;
int v[NMAX];
int t[NMAX];
double s[NMAX];

bool ok(double val) {
    for (int i = 1; i <= n; i++) {
        s[i] = s[i - 1] + v[i] - val * t[i];
    }
    deque<int>q;
    for(int i=l;i<=n;i++){
        while(!q.empty() && s[i-l] <= s[q.back()]){
            q.pop_back();
        }
        q.push_back(i-l);
        if(i - q.front() == u){
            q.pop_front();
        }
        if(s[i] - s[q.front()] >= 0.0){
            return 1;
        }

    }
    return 0;
}

double cb() {
    double st = 0.0, dr = 1000.0, last;
    while (dr - st >= EPS) {
        double mid = (st + dr) / 2;
        if (ok(mid)) {
            st = mid + EPS;
            last = mid;
        } else {
            dr = mid - EPS;
        }
    }
    return last;
}

int main() {
    freopen("secv3.in","r",stdin);
    freopen("secv3.out","w",stdout);
    scanf("%d %d %d", &n, &l, &u);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &t[i]);
    }
    printf("%0.2f", cb());

    return 0;
}