Cod sursa(job #1374769)

Utilizator retrogradLucian Bicsi retrograd Data 5 martie 2015 10:42:55
Problema Secventa 3 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<fstream>
#include<vector>

using namespace std;
typedef int var;

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

#define MAXN 30000
#define MAX 1000001

var V[MAXN], P[MAXN];
double VECT[MAXN];
var n;
var log[MAXN];
double RMQ[20][MAXN];
var L, U;

void build_log() {
    for(var i=2; i<=n; i++) {
        log[i] = log[i/2] + 1;
    }
}


void build_rmq() {
    for(var i=1; (1<<i) <= n; i++) {
        for(var j=1; j+(1<<i)-1 <= n; j++) {
            RMQ[i][j] = min(RMQ[i-1][j], RMQ[i-1][j+(1<<(i-1))]);
        }
    }
}

double query(var b, var e) {
    var l = log[e-b+1];
    return min(RMQ[l][b], RMQ[l][e-(1<<l)+1]);
}


double solve(double val) {
    for(var i=1; i<=n; i++) {
        RMQ[0][i] = V[i] - val * P[i];
        RMQ[0][i] += RMQ[0][i-1];
    }

    build_rmq();
    double m = -MAX;

    for(var i=L; i<=U; i++) {
        m = max(m, RMQ[0][i] - query(0, i-L));
    }
    for(var i=U+1; i<=n; i++) {
        m = max(m, RMQ[0][i] - query(i-U, i-L));
    }
    return m;
}

int main() {
    fin>>n>>L>>U;
    build_log();
    for(var i=1; i<=n; i++) {
        fin>>V[i];
    }
    for(var i=1; i<=n; i++) {
        fin>>P[i];
    }

    double num = 0, i;

    //solve(0);

    for(i = MAX; i>=1e-3; i/=2) {
        if(num + i <= MAX && solve(num + i) > 0) {
            num += i;
        }
    }
    fout<<num;
}