Pagini recente » Cod sursa (job #1141125) | Cod sursa (job #1669509) | Cod sursa (job #339001) | Cod sursa (job #2300584) | Cod sursa (job #316442)
Cod sursa(job #316442)
#include <cstdio>
#include <cstring>
#define maxn 30100
using namespace std;
int c[maxn], t[maxn];
int n, i, j, l, u;
double p[maxn], sum[maxn], rez;
int deq[maxn], sus, jos;
inline bool posibil(double d) {
int i, j;
for (i = 1; i <= n; i++)
p[i] = c[i] - (t[i] * d);
for (i = 1; i <= n; i++)
sum[i] = sum[i - 1] + p[i];
sus = 0; jos = 1;
memset(deq, 0, sizeof(deq));
for (i = 1; i <= n; i++) {
if (i - l > 0) {
while (sum[i - l] < sum[deq[sus]] && sus >= jos)
sus--;
sus++;
deq[sus] = i - l;
}
while (deq[jos] <= i - u && jos <= sus)
jos++;
if (sum[i] - sum[deq[jos]] >= 0)
return true;
}
return false;
}
void bsearch(double left, double right) {
double m;
while (left + 0.0001 <= right) {
m = (left + right) / 2;
// printf("%.3lf\n %d", m, posibil(m));
if (posibil(m)) {
if (m > rez)
rez = m;
left = m + 0.001;
}
else
right = m - 0.001;
}
}
int main() {
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", &c[i]);
for (i = 1; i <= n; i++)
scanf("%d", &t[i]);
bsearch(0, 30000000);
// printf("%d\n", posibil(2.5));
printf("%.2lf\n", rez);
return 0;
}