Cod sursa(job #1509983)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 24 octombrie 2015 14:39:01
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMax = 3e4 + 5;
const int Lim = 1e5;

int n, l, u;
int c[NMax], t[NMax];
long long int S[NMax];

deque < int > D;

inline bool Good(const int &x){
    for(int i = 1; i <= n; i++){
        S[i] = S[i - 1] + c[i] - 1LL * t[i] * x;
    }
    D.clear();
    for(int i = l; i <= n; i++){
        while(!D.empty() && S[i - l] <= S[D.back()]){
            D.pop_back();
        }
        while(!D.empty() && i - D.front() > u){
            D.pop_front();
        }
        D.push_back(i - l);
        if(!D.empty() && S[i] - S[D.front()] >= 0){
            return 1;
        }
    }
    return 0;
}

inline int Solve(){
    int step = (1 << 20), i;
    for(i = 0; step; step >>= 1){
        if(i + step <= Lim && Good(i + step)){
            i += step;
        }
    }
    return i;
}

int main(){
    fin >> n >> l >> u;
    for(int i = 1; i <= n; i++){
        fin >> c[i];
        c[i] *= 100;
    }
    for(int i = 1; i <= n; i++){
        fin >> t[i];
    }
    fout << 1.00 * Solve() / 100;
    return 0;
}