Pagini recente » Cod sursa (job #2283139) | Cod sursa (job #2020940) | Cod sursa (job #1063131) | iconcurs17 | Cod sursa (job #597072)
Cod sursa(job #597072)
#include <cstdio>
using namespace std;
const int N = 100005;
int a[N], b[N], U, L, n;
int ok(double v) {
int d[N], front = 1, back = 0, i;
double s[N];
s[0] = 0;
for(i = 1; i <= n; ++i)
s[i] = (double)s[i - 1] + ((double)a[i] -(double) b[i] * v);
// for(i = 1; i <= n; ++i)
// printf("%.2lf\n", s[i]);
for(i = L ; i <= n; ++i) {
while(front <= back && s[d[back]] > s[i - L])
--back;
d[++back] = i - L;
if(s[i] - s[d[front]] >= 0)
return 1;
if(i - L - d[front] +1 == U)
++front;
}
return 0;
}
int main(){
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
int i, j;
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]);
const double eps = 0.0001;
double rez = 0, step = 10000;
for(; step > eps; step /= 2)
if(ok(rez + step)){
// printf("%.2lf %.2lf\n", rez, step);
rez += step;
}
printf("%.2lf\n", rez);
return 0;
}