Pagini recente » Cod sursa (job #1023801) | Cod sursa (job #2189861) | Cod sursa (job #2557752) | Cod sursa (job #2370071) | Cod sursa (job #409504)
Cod sursa(job #409504)
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define FIN "secv3.in"
#define FOUT "secv3.out"
#define MAX_N 30005
#define INF 0x3f3f3f3f
double C[MAX_N];
double T[MAX_N];
int N, L, U;
double v[MAX_N];
int d[MAX_N]; // deque
inline double max (double a, double b)
{
return (a > b) ? a : b;
}
int compute (double X)
{
memset(v, 0, sizeof (v));
memset(d, 0, sizeof (d));
double localBEST = -INF;
for (int i = 1; i <= N; ++i)
v[i] = C[i] - X * T[i] + v[i - 1];
int li, lf;
for (int i = 1, li = lf = 0; i <= N; ++i)
{
if (i - d[li] > U) ++li;
if (i - d[li] >= L && li <= lf)
localBEST = max(localBEST, v[i] - v[d[li]]);
d[++lf] = i;
while (lf > li && v[d[lf]] < v[d[lf - 1]]) d[--lf] = d[lf + 1];
}
//printf("%.10lf\n", localBEST);
if (localBEST < 0)
return 0;
else
return 1;
}
int main ()
{
freopen (FIN, "r", stdin);
freopen (FOUT, "w", stdout);
scanf ("%d %d %d", &N, &L, &U);
for (int i = 1; i <= N; ++i) scanf ("%lf", C + i);
for (int i = 1; i <= N; ++i) scanf ("%lf", T + i);
double li = 0, lf = 1010, m;
while (abs(li - lf) > 0.001)
if (compute(m = (li + lf) / 2)) li = m + 0.001;
else lf = m - 0.001;
printf ("%lf\n", m);
return 0;
}