Cod sursa(job #1556775)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 25 decembrie 2015 21:59:00
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream in("secv3.in");
ofstream out("secv3.out");

const int MAX_N = 30000;
const int BSLIM = 100000;

int n, l, u;
int A[1 + MAX_N];
int B[1 + MAX_N];
long long D[1 + MAX_N];

void build_array(int X) {
    int i;
    for(i = 1; i <= n; i++) {
        D[i] = D[i-1] + A[i] * 100 - X * B[i];
    }
}

bool bs_check(int X) {
    int i;
    deque < long long > minQ;

    build_array(X);
    for(i = 1; i <= n; i++) {
        if(!minQ.empty() && minQ.front() < i - u) {
            minQ.pop_front();
        }
        if(i - l >= 0) {
            while(!minQ.empty() && D[i-l] <= D[minQ.back()]) {
                minQ.pop_back();
            }
            minQ.push_back(i-l);
        }
        if(!minQ.empty()) {
            if(D[i] - D[minQ.front()] >= 0) return 1;
        }
    }

    return 0;
}

int b_search() {
    int l = 1, r = BSLIM, m, best = -1;

    while(l <= r) {
        m = (l + r) / 2;
        if(bs_check(m) == 1) {
            best = m;
            l = m + 1;
        }
        else r = m - 1;
    }

    return best;
}

int main() {
    int i;

    in >> n >> l >> u;
    for(i = 1; i <= n; i++) in >> A[i];
    for(i = 1; i <= n; i++) in >> B[i];

    out << (double)b_search() / 100 << '\n';

    return 0;
}