Pagini recente » Cod sursa (job #2398372) | Cod sursa (job #174372) | Cod sursa (job #1178168) | Istoria paginii runda/testasd/clasament | Cod sursa (job #203083)
Cod sursa(job #203083)
#include<stdio.h>
#define lg 30005
#define lint long long
int n, i, u, l;
lint v[lg], w[lg];
double rezultat;
struct deq{
lint v;
int i;
};
deq q[lg];
inline lint max(lint a, lint b){
return a > b ? a : b;
}
bool check(lint val){
int i, st = 1, end = 0, j;
lint rez, d[lg] = {0};
for (i = 1; i <= n; i ++){
d[i] = d[i-1] + v[i] - w[i]*val;
// printf("%d ", v[i] - w[i]*val);
}
for (i = u; i <= l; i ++){
while (st <= end && d[i] >= q[end].v)
end --;
q[++end].v = d[i];
q[end].i = i;
}
rez = q[1].v;
for (i = l+1; i <= n; i ++){
if (st <= end && q[st].i == i-l+u-1)
st ++;
while (st <= end && d[i] >= q[end].v)
end --;
q[++end].v = d[i];
q[end].i = i;
rez = max(rez, q[st].v - d[i-l]);
}
for (i = n-l+1, j = n-(l-u); i < n; i ++, j ++){
if (st <= end && q[st].i == j)
st ++;
if (st <= end)
rez = max(rez, q[st].v - d[i]);
}
// printf("%d\n", rez);
if (rez >= 0)
return 1;
return 0;
}
lint bs(){
lint li = 1, ls = 2000000000, x, gs = 0;
while (li <= ls){
x = (li+ls) / 2;
// printf("%d\n", x);
if (check(x)){
gs = x;
li = x+1;
}
else
ls = x-1;
}
return gs;
}
int main()
{
freopen("secv3.in", "rt", stdin);
freopen("secv3.out", "wt", stdout);
scanf("%d%d%d", &n, &u, &l);
for (i = 1; i <= n; i ++){
scanf("%lld", &v[i]);
v[i] *= 100;
}
for (i = 1; i <= n; i ++)
scanf("%lld", &w[i]);
rezultat = (double)bs();
// printf("%d\n", check(83));
printf("%.2lf\n", rezultat / 100);
return 0;
}