Cod sursa(job #489250)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 1 octombrie 2010 23:44:45
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>

#include <set>

using namespace std;

int n, l, u;
double v[30002], t[30002], d[30002], sp[30002];

int exista (double x)
{
	int i;
	set <double> h;
	
	for (i = 1; i <= n; i ++)
		d[i] = v[i] - t[i] * x;
	for (i = 1; i <= n; i ++)
		sp[i] = sp[i - 1] + d[i];
	
	for (i = l; i <= n; i ++)
	{
		h.insert (sp[i - l]);
		if (i >= u)
			h.erase (sp[i - u]);
		if (sp[i] - *h.begin () >= 0)
			return 1;
	}
	return 0;
}

int main ()
{
	freopen ("secv3.in", "r", stdin);
	freopen ("secv3.out", "w", stdout);
	
	scanf ("%d %d %d", &n, &l, &u);
	
	int i;
	
	for (i = 1; i <= n; i ++)
		scanf ("%lf", &v[i]);
	for (i = 1; i <= n; i ++)
		scanf ("%lf", &t[i]);
	
	double st = 0, dr = 1000, m, sol;
	
	for (i = 1; i <= 20; i ++)
	{
		m = (st + dr) * 0.5;
		if (exista (m))
		{
			st = m + 1;
			sol = m;
		}
		else
			dr = m - 1;
	}
	printf ("%lf", sol);
	
	return 0;
}