Cod sursa(job #827239)

Utilizator Marius96Marius Gavrilescu Marius96 Data 1 decembrie 2012 21:04:38
Problema Secventa 3 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<iomanip>
using namespace std;

int n,x,y,m,p,u,z,l,r,ok,i,j,a[30001],b[30001];
long long c[30005],d[30005];

int main()
{
	ifstream f("secv3.in");
	ofstream g("secv3.out");
	f >> n >> x >> y;
	z=y-x+1;
	for (i=1;i<=n;i++)
	{
		f >> a[i];
		a[i]*=1000;
	}
	for (i=1;i<=n;i++)
		f >> b[i];
	p=1;u=1000000;
	while (p<=u)
	{
		m=(p+u)/2;
		for (i=1;i<=n;i++)
			c[i]=c[i-1]+a[i]-m*b[i];
		l=1;r=0;ok=1;
		if (c[x]>=0)
			ok=0;
		for (i=1;i<n;i++)
		{
			while ((r>0) && (c[i]<d[r]))
				r--;
			d[++r]=c[i];
			if ((i>z) && (c[i-z]==d[l]))
				l++;
			if (i>=z)
				if (c[i+x]-d[l]>=0)
					ok=0;
		}
		if (c[n]-d[l]>=0)
			ok=0;
		if (ok==0)
			p=m+1;
		else u=m-1;
	}
	g << setprecision(3) << fixed << (double)m/1000;
	return 0;
}