Cod sursa(job #759893)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 19 iunie 2012 19:33:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <cstdio>
#include <deque>

using namespace std;

const int maxn = 30005;
deque <int> deq;
int n, l, u, v[maxn], t[maxn];
double s[maxn];

bool verifica(double x)
{
    int i;
    for(i = 1; i <= n; ++i)
        s[i] = s[i - 1] + v[i] - x * t[i];
    deq.clear();
    for(i = l; i <= n; ++i) {
        while(!deq.empty() && s[i - l + 1] <= s[deq.back()])
            deq.pop_back();
        deq.push_back(i - l);
        while(i - u - 1 >= deq.front())
            deq.pop_front();
        if(s[i] - s[deq.front()] >= 0)
            return true;
    }
    return false;
}

double cauta()
{
    double left = 0, right = 50000, sol, mij;
    while(left < right) {
        mij = (left + right) / 2;
        if(verifica(mij)) {
            sol = mij;
            left = mij + 0.001;
        }
        else
            right = mij - 0.001;
    }
    return sol;
}


int main()
{
    int i;
    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", &v[i]);
    for(i = 1; i <= n; ++i)
        scanf("%d", &t[i]);
    printf("%lf", cauta());

    return 0;
}