Cod sursa(job #480839)

Utilizator ooctavTuchila Octavian ooctav Data 29 august 2010 20:28:10
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;

#define c first
#define t second
const int NMAX = 30005;
const int INF = 1000000000;

long long N, L, U;
long long P = 1LL<<60, REZ = 0;
pair<long long, long long> a[NMAX];
pair<long long, long long> sum[NMAX];
pair<long long, long long> best[NMAX];
long long back;


void citire()
{
	long long 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()
{
	back = 1;
	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;
		
		if(i - back == U)
		{
			best[i - 1].c -= best[back].c;
			best[i - 1].c -= best[back].c;
			back++;
		}
		
		if((best[i - 1].c + a[i].c) / (best[i - 1].t + a[i].t) > a[i].c/a[i].t)
		{
			best[i].c = best[i - 1].c + a[i].c;
			best[i].t = best[i - 1].t + a[i].t;
		}
		else
		{
			best[i].c = a[i].c;
			best[i].t = a[i].t;
			back = i;
		}
	}
}

int medie(long long scad)
{
	long long medie = -INF;
	for(int i = L ; i <= N ; i++)
	{
		long long md = (sum[i].c - sum[i - L + 1].c + best[i - L + 1].c) - scad*(sum[i].t - sum[i - L + 1].t + best[i - L + 1].t);
		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("%.2lf\n", (double)REZ/100);
	return 0;
}