Pagini recente » Cod sursa (job #2504459) | Cod sursa (job #497404) | Cod sursa (job #3139316) | Cod sursa (job #994697) | Cod sursa (job #480826)
Cod sursa(job #480826)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define c first
#define t second
const int NMAX = 30005;
const int INF = 1000000000;
int N, L, U;
int P = 1<<30, REZ = 0;
pair<int, int> a[NMAX];
pair<int, int> sum[NMAX];
pair<int, int> best[NMAX];
int begin[NMAX];
pair<int, int> pred;
void citire()
{
int x;
cin >> N >> L >> U;
for(int i = 1 ; i <= N ; i++)
{
cin >> x;
a[i].c = 1000 * x;
}
for(int i = 1 ; i <= N ; i++)
cin >> a[i].t;
}
void calcul_vectori()
{
int sch;
begin[1] = 1;
for(int i = 1 ; i <= N ; i++)
{
sum[i].c = a[i].c + sum[i - 1].c;
sum[i].t = a[i].t + sum[i - 1].t;
pred = best[i - 1];
sch = 0;
if(i - begin[i - 1] == U)
{
pred.c -= a[i - U].c;
pred.t -= a[i - U].t;
sch = 1;
}
if((pred.c + a[i].c) / (pred.t + a[i].t) > a[i].c/a[i].t)
{
best[i].c = pred.c + a[i].c;
best[i].t = pred.t + a[i].t;
begin[i] = begin[i - 1] + sch;
}
else
{
best[i].c = a[i].c;
best[i].t = a[i].t;
begin[i] = i;
}
}
}
int medie(int scad)
{
int medie = -INF;
for(int i = L ; i <= N ; i++)
{
int md = (sum[i].c - sum[i - L + 1].c + best[i - L + 1].c) / (sum[i].t - sum[i - L + 1].t + best[i - L + 1].t);
md -= scad;
medie = max(medie, md);
}
return medie;
}
void caut_bin()
{
while(P)
{
int x = medie(P + REZ);
if(x >= 0)
REZ += P;
if(x == 0)
return;
P >>= 1;
}
}
int main()
{
freopen("secv3.in", "r", stdin);
freopen("secv3.out", "w", stdout);
citire();
calcul_vectori();
caut_bin();
printf("%.2lf\n", (double)REZ/1000);
return 0;
}