Cod sursa(job #1804956)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 13 noiembrie 2016 12:23:46
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 30003;

int n, st, dr, mid, A[Nmax], B[Nmax], L, U, i;

bool check(int x)
{
    int i;
    long long a[Nmax];
    deque<int> dq;

    for(i=1; i<=n; ++i)
        a[i] = a[i-1] + A[i] - B[i]*x;

    for(i=L; i<=n; ++i)
    {
        if(dq.size() && dq.front()==i-U-1) dq.pop_front();
        while(dq.size() && a[dq.back()] >= a[i-L]) dq.pop_back();
        dq.push_back(i-L);

        if(a[i] - a[dq.front()] >= 0) return 1;
    }

    return 0;
}

int main()
{
    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", &A[i]), A[i] *= 100;
    for(i=1; i<=n; ++i) scanf("%d", &B[i]);

    st=0; dr=100*1000;

    while(st<=dr)
    {
        mid = (st+dr)>>1;
        if(check(mid)) st = mid+1;
        else dr = mid-1;
    }

    printf("%.2lf\n", (double)dr/100);

    return 0;
}