Pagini recente » Cod sursa (job #975623) | Cod sursa (job #763294) | Cod sursa (job #3179455) | Cod sursa (job #3004052) | Cod sursa (job #480805)
Cod sursa(job #480805)
#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<<17, 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 = 100 * x;
}
for(int i = 1 ; i <= N ; i++)
cin >> a[i].t;
}
void calcul_vectori()
{
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];
if(i - begin[i] == U)
{
best[i].c -= a[i - U].c;
best[i].t -= a[i - U].t;
begin[i]++;
}
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];
}
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 *(i - begin[i - L + 1] + 1);
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("%.2f\n", (float)REZ/100);
return 0;
}