Cod sursa(job #480832)

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

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

int N, L, U;
long long P = 1LL * 1<<40, 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 begin[NMAX];
pair<long long, long long> pred;

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()
{
	int sch;
	begin[1] = 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;
		pred = best[i - 1];
		sch = 0;
		
		if(i - begin[i - 1] == U)
		{
			pred.c -= a[i - U].c;
			pred.t -= a[i - U].t;
			sch = 1;
		}
		
		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] + sch;
		}
		else
		{
			best[i].c = a[i].c;
			best[i].t = a[i].t;
			begin[i] = i;
		}
	}
}

int medie(int 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) / (sum[i].t - sum[i - L + 1].t + best[i - L + 1].t);
		md -= scad;
		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", (long double)REZ/100);
	return 0;
}