Pagini recente » Cod sursa (job #1502086) | Cod sursa (job #978291) | Cod sursa (job #3206897) | Cod sursa (job #1634668) | Cod sursa (job #733755)
Cod sursa(job #733755)
//Sursa luata de la prietena mea Malina, nu-i asa ca e o fata pe cinste? :P
#include <stdio.h>
#include <string.h>
#define LMAX 30100
int N, P, q;
int A[LMAX], B[LMAX], Q[LMAX];
double sum[LMAX];
bool possible (double val)
{
int i, p, u;
double best = -1, now;
memset (Q, 0, sizeof (Q));
sum[0] = 0; p = u = 1;
for (i = 1; i <= N; i ++)
sum[i] = sum[i - 1] + A[i] - val * B[i];
for (i = P; i <= N; i ++)
{
now = sum[i] - sum[Q[p]];
if (now > best)
best = now;
while (p <= u && sum[Q[u]] >= sum[i - P + 1])
u --;
Q[++ u] = i - P + 1;
if (Q[p] + q == i)
p ++;
}
return best > 0;
}
double binary_search ()
{
int left = 1, right = (1 << 30);
double med, last;
while (left <= right)
{
med = (double)(left + right) / 200.0;
if (possible (med))
left = (left + right) / 2 + 1, last = med;
else
right = (left + right) / 2 - 1;
}
return last;
}
int main ()
{
freopen ("secv3.in", "r", stdin);
freopen ("secv3.out", "w", stdout);
scanf ("%d%d%d", &N, &P, &q);
int i;
for (i = 1; i <= N; i ++)
scanf ("%d", &A[i]);
for (i = 1; i <= N; i ++)
scanf ("%d", &B[i]);
printf ("%.2lf", binary_search ());
return 0;
}