Cod sursa(job #2890944)

Utilizator mateicosCostescu Matei mateicos Data 17 aprilie 2022 01:47:57
Problema Secventa 3 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <cstdio>
#include <deque>

using namespace std;

deque<int>q;

int v[30005], t[30005];
double s[30005];
int n, l, r;

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

double bs(double st, double dr){
    double med;
    int i;
    for(i = 0;i < 40;i++){
        med = (st + dr) / 2;
        if(ok(med))
            st = med;
        else
            dr = med;
    }
    return med;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    int i, j, sv = 0, st = 0;
    double x, s = 0., sol;
    scanf("%d%d%d", &n, &l, &r);
    for(i = 1;i <= n;i++){
        scanf("%d", &v[i]);
    }
    for(i = 1;i <= n;i++){
        scanf("%d", &t[i]);
    }

    printf("%lf", bs(0.0, 1000.0));
    return 0;
}