Pagini recente » Cod sursa (job #2822657) | Cod sursa (job #442013) | Cod sursa (job #3180148) | Cod sursa (job #104993) | Cod sursa (job #1374781)
#include<fstream>
#include<vector>
using namespace std;
typedef int var;
ifstream fin("secv3.in");
ofstream fout("secv3.out");
#define MAXN 30002
#define MAX 10000001
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;
}