Pagini recente » Cod sursa (job #559303) | Cod sursa (job #895209) | Cod sursa (job #2784408) | Cod sursa (job #132454) | Cod sursa (job #480833)
Cod sursa(job #480833)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define c first
#define t second
const int NMAX = 30005;
const int INF = 1000000000;
long long N, L, U;
long long P = 1LL<<60, REZ = 0;
pair<long long, long long> a[NMAX];
pair<long long, long long> sum[NMAX];
pair<long long, long long> best[NMAX];
long long begin[NMAX];
pair<long long, long long> pred;
void citire()
{
int x;
cin >> N >> L >> U;
for(int i = 1 ; i <= N ; i++)
{
cin >> x;
a[i].c = 100 * 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(long long scad)
{
long long medie = -INF;
for(int i = L ; i <= N ; i++)
{
long long 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", (long double)REZ/100);
return 0;
}