Pagini recente » Cod sursa (job #2780966) | Cod sursa (job #942695) | Cod sursa (job #242645) | Cod sursa (job #1104868) | Cod sursa (job #596757)
Cod sursa(job #596757)
#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] + a[i] -(double) b[i] * v;
// for(i = 1; i <= n; ++i)
// printf("%.2lf\n", s[i]);
for(i = 1; i <= n; ++i) {
while(front <= back && s[d[back]] > s[i - 1])
--back;
d[++back] = i - 1;
if(i >= L){
if(s[i] - s[d[front]] >= 0)
return 1;
if(i - 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.001;
double rez = 0, step = 1000;
for(; step > eps; step /= 2)
if(ok(rez + step)){
// printf("%.2lf %.2lf\n", rez, step);
rez += step;
}
printf("%.2lf\n", rez);
return 0;
}