Cod sursa(job #1783051)

Utilizator grimmerFlorescu Luca grimmer Data 18 octombrie 2016 18:48:43
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <fstream>
#include <deque>
using namespace std;

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

const int NMAX = 30069, RMAX = 1<<30;
const double eps = 1.e-2;
int c[NMAX], t[NMAX];
int n, l, u;

double check(double x){
    double p[NMAX], sp[NMAX], sum_secv, max_sum = -1.00 * (double)RMAX;
    deque<int> q;
    int i;

    for(i = 1; i <= n; ++i){
        p[i] = (double)c[i] - x * (double)t[i];
        sp[i] = sp[i - 1] + p[i];
    }

    for(i = 1; i <= n; ++i){

        if(i-l+1 > 0){

            while(!q.empty() && sp[q.back()] >= sp[i - l]){
                q.pop_back();
            }

            q.push_back(i - l);

            while(!q.empty() && q.front() <= i - u - 1){
                q.pop_front();
            }

            sum_secv = sp[i] - sp[q.front()];
            max_sum = max(max_sum, sum_secv);
        }

    }

    return max_sum;
}

int Bin_search(int lf, int r){
    int m, x;

    while(lf < r){
        m = (lf + r) / 2;

        if(check((double)m / 100.00) >= 0){
            lf = m + 1;
            x = m;
        }
        else{
            r = m - 1;
        }
    }

    return x;
}

int main()
{
    int i;
    fin>>n>>l>>u;

    for(i = 1; i <= n; ++i){
        fin>>c[i];
    }

    for(i = 1; i <= n; ++i){
        fin>>t[i];
    }

    fout<<(double)Bin_search(0, RMAX) / 100;
    return 0;
}