Pagini recente » Cod sursa (job #1290477) | Cod sursa (job #604558)
Cod sursa(job #604558)
#include <stdio.h>
#include <deque>
#define MAXN 35000
int n,gl,gu;
int cost[MAXN];
int timp[MAXN];
using namespace std;
int calculeaza(int len)
{
if (len < gl || len > gu) return 0;
int totalSum = 0;
int totalDiv = 0;
for (int i = 0 ; i < len ; ++i)
{
totalSum += cost[i];
totalDiv += timp[i];
}
int best = totalSum / totalDiv;
for (int i = len; i < n ; ++i)
{
totalSum -= cost[i - len];
totalDiv -= timp[i - len];
totalSum += cost[i];
totalDiv += timp[i];
if (totalSum / totalDiv > best) best = totalSum / totalDiv;
}
return best;
}
int cauta(int l,int u)
{
if ( u < l) return 0;
if ( u > gu) return 0;
if ( l < gl) return 0;
int mid = (l + u) / 2;
int cmid = calculeaza(mid);
int cs = calculeaza((l + mid - 1) / 2);
int cr = calculeaza((u + mid + 1) / 2);
if ( cs > cmid)
return cauta(l,mid - 1);
if ( cr > cmid)
return cauta(mid + 1,u);
return cmid;
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&n,&gl,&gu);
for (int i = 0 ; i < n ; ++i)
{
scanf("%d",&cost[i]);
cost[i] *= 100;
}
for (int i = 0; i < n ; ++i)
scanf("%d",&timp[i]);
int rez = cauta(gl,gu);
printf("%d.%d\n",rez / 100,rez % 100);
return 0;
}