Cod sursa(job #604559)

Utilizator sergiupPopescu Sergiu sergiup Data 23 iulie 2011 14:42:44
Problema Secventa 3 Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#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] *= 1000;
	}

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

	printf("%d.%d\n",rez / 1000,(rez % 1000) / 10);
	
	return 0;
}