Cod sursa(job #604569)

Utilizator sergiupPopescu Sergiu sergiup Data 23 iulie 2011 14:53:54
Problema Secventa 3 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <deque>
#define MAXN 35000

int n,gl,gu;
double cost[MAXN];
double timp[MAXN];

using namespace std;

double calculeaza(int len)
{
	if (len < gl || len > gu) return 0;
	double totalSum = 0;
	double totalDiv = 0;
	for (int i = 0 ; i < len ; ++i)
	{
		totalSum += cost[i];
		totalDiv += timp[i];
	}

	double 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;
}

double 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;

	double cmid = calculeaza(mid);
	double cs = calculeaza(mid - 1);
	double cr = calculeaza(mid + 1);

	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("%lf",&cost[i]);

	for (int i = 0; i < n ; ++i)
		scanf("%lf",&timp[i]);
	
	double rez = cauta(gl,gu);

	printf("%.2lf",rez);
	
	return 0;
}