Pagini recente » Cod sursa (job #1596231) | Cod sursa (job #783251) | Cod sursa (job #2629895) | Cod sursa (job #1192336) | Cod sursa (job #1259156)
#include <cstdio>
#include <iomanip>
#include <fstream>
using namespace std;
int n, l, r;
int c [30002], t [30002];
long long x [30002], sp [30002];
bool verif (int value) {
int i, minD [30002], p, u, st, dr;
long long h;
//value = 100000000; // !!
for (i = 1; i <= n; i ++) {
x [i] = (long long)c [i] - t [i] * value;
sp [i] = (long long)sp [i - 1] + x [i];
}
u = p = 1;
minD [1] = 0;
st = 0;
dr = 0;
for (i = l; i <= n; i ++) {
h = sp [i] - sp [minD [p]];
if (h >= 0)
return 1;
++ dr;
while (p <= u && sp [dr] < sp [minD [p]])
p ++;
minD [++ u] = dr;
if (i + 1 - st > r) {
st ++;
while (p <= u && i - minD [p] > r)
p ++;
}
}
return 0;
}
int main () {
int i, st, dr, m, last;
double ans;
freopen ("secv3.in", "r", stdin);
ofstream fout ("secv3.out");
scanf ("%d%d%d", &n, &l, &r);
for (i = 1; i <= n; i ++) {
scanf ("%d",&c [i]);
c [i] = c [i] * 1000;
}
for (i = 1; i <= n; i ++)
scanf ("%d", &t [i]);
st = 1;
dr = 40000000;
while (st <= dr) {
m = (st + dr) / 2;
if (verif (m)) {
last = m;
st = m + 1;
}
else dr = m - 1;
}
ans = (double)last / 1000;
fout << fixed << setprecision(2) << ans;
return 0;
}