Cod sursa(job #793614)

Utilizator visanrVisan Radu visanr Data 3 octombrie 2012 17:18:17
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <cstdio>
#include <cstdlib>
#include <deque>
using namespace std;

#define eps 0.01
#define nmax 30010
#define pf push_front
#define pb push_back
#define ppb pop_back
#define ppf pop_front

int A[nmax], B[nmax], N, L, U;
double S[nmax];


bool Check(double mid)
{
    int i;
    deque<int> D;
    for(S[0] = 0, i = 1; i <= N; i++)
        S[i] = S[i - 1] + 1.0 * A[i] - mid * B[i];
    D.pf(0);
    for(i = L; i <= N; i++)
    {
        while(!D.empty() && S[i - L] < S[D.back()])
            D.ppb();
        D.pb(i - L);
        if(D.front() == i - U - 1) D.ppf();
        if(S[i] >= S[D.front()]) return true;
    }
    return false;
}

double BS()
{
    double ans, left = 0, right = 1000, mid;
    while(left < right)
    {
        mid = (left + right) / 2;
        if(Check(mid))
            ans = mid, left = mid + eps;
        else
            right = mid - eps;
    }
    return ans;
}

int main()
{
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    int i;
    scanf("%i %i %i", &N, &L, &U);
    for(i = 1; i <= N; i++)
        scanf("%i", &A[i]);
    for(i = 1; i <= N; i++)
        scanf("%i", &B[i]);
    printf("%.2lf\n", BS());
    return 0;
}