Cod sursa(job #1289403)

Utilizator iulian_moneIulian Mone iulian_mone Data 9 decembrie 2014 20:59:57
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>
#include<algorithm>
#include<deque>

#define NMAX 5000007
#define LL long long
#define INF 1000000000

using namespace std;

deque < int > Deq;
int n, L, U;
int a[NMAX], b[NMAX];
double Sum[NMAX];

int check(double med){
    Sum[0] = 0;
    Deq.clear();
    double Ans = - INF;
    for(int i = 1; i <= n; ++ i)
        Sum[i] = (double) Sum[i - 1] + a[i] - med * b[i];
    for(int i = L; i <= n; ++ i){
        if(! Deq.empty())
            Ans = max(Ans, Sum[i] - Sum[Deq.front()]);
        while(! Deq.empty() && Sum[Deq.back()] >= Sum[i - L + 1])
            Deq.pop_back();
        Deq.push_back(i - L + 1);
        if(Deq.front() + U == i)
            Deq.pop_front();
    }
    return Ans > 0;
}

double cb(){
    int st = 1, dr = (1 << 30);
    double med, last = -1;
    while(st <= dr){
        med = (double) (st + dr) / 200.0;
        if(check(med) == 1){
            st = ((st + dr) >> 1) + 1;
            last = med;
        }
        else
            dr = ((st + dr) >> 1) - 1;
    }
    return last;
}

int main(){
    freopen("secv3.in", "r", stdin);
    freopen("secv3.out", "w", stdout);
    LL Ans = -10000000000000;
    scanf("%d %d %d", &n, &L, &U);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++ i)
        scanf("%d", &b[i]);
    printf("%.2f", cb());
    return 0;
}