Pagini recente » Cod sursa (job #1040501) | Cod sursa (job #841600) | Cod sursa (job #802432) | Monitorul de evaluare | Cod sursa (job #316389)
Cod sursa(job #316389)
#include <stdio.h>
#define MAX_N 30010
int n, l, u, i, ok, p, q;
int A[MAX_N], B[MAX_N], deq[MAX_N];
double sum[MAX_N];
double st, dr, mid, sol;
void cit() {
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
scanf("%d %d %d", &n, &l, &u);
for (i = 1; i <= n; i++)
scanf("%d", &A[i]);
for (i = 1; i <= n; i++)
scanf("%d", &B[i]);
}
void deq_push(int i) {
deq[++q] = i;
while (sum[deq[q]] > sum[deq[q - 1]] && q > p) {
deq[q - 1] = deq[q];
deq[q--] = 0;
}
}
void deq_pop(int i) {
while (deq[p] < i && p <= q)
p++;
}
void solve() {
st = 0; dr = 1000000000;
while (st + 0.0001 < dr) {
mid = (double) (st + dr) / 2;
for (i = 1; i <= n; i++)
sum[i] = (double) sum[i - 1] + A[i] - mid * B[i];
p = 1; q = 0;
for (i = l; i <= u; i++)
deq_push(i);
ok = 0;
for (i = 1; i <= n; i++) {
if (sum[deq[p]] >= sum[i - 1]) {
ok = 1;
break;
}
deq_pop(i + l);
if (i + u <= n)
deq_push(i + u);
if (p > q) break;
}
if (ok) {
if (mid > sol) sol = mid;
st = mid;
}
else dr = mid;
}
printf("%.3lf\n", sol);
}
int main() {
cit();
solve();
return 0;
}