Cod sursa(job #480805)

Utilizator ooctavTuchila Octavian ooctav Data 29 august 2010 17:13:24
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#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;
}