Cod sursa(job #1557200)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 decembrie 2015 23:33:21
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>
#include <deque>

#define DIM 32768
#define INF 1048576
using namespace std;

int L, R, N, mid, st, dr;
int V[DIM], T[DIM]; long long S[DIM];
deque <long long> Deque;

inline bool getAnswer (int val) {

    for (int i = 1; i <= N; i ++)
        S[i] = S[i-1] + V[i] * 100 - T[i] * val;
    Deque.clear();

    for (int i = L; i <= N; i ++) {

        while (!Deque.empty() && S[i-L] <= S[Deque.back()])
            Deque.pop_back();
        Deque.push_back(i - L);

        if (i - Deque.front() == R)
            Deque.pop_front();

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

    return 0;
}

int main () {

    freopen ("secv3.in" ,"r", stdin );
    freopen ("secv3.out","w", stdout);

    scanf ("%d %d %d", &N, &L, &R);

    for (int i = 1; i <= N; i ++)
        scanf ("%d", &V[i]);

    for (int i = 1; i <= N; i ++)
        scanf ("%d", &T[i]);

    st = 1; dr = 1048576;
    while (st <= dr) {
        mid = st + (dr - st) / 2;

        if (getAnswer (mid))
            st = mid + 1;
        else
            dr = mid - 1;
    }

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

    return 0;
}