Cod sursa(job #509501)

Utilizator loginLogin Iustin Anca login Data 11 decembrie 2010 11:14:56
Problema Secventa 3 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
# include <fstream>
# include <iostream>
# include <cstdio>
# define DIM 30003
using namespace std;
int n, l, u, c[DIM], t[DIM], dq[DIM], sol;
long long v[DIM];

void read ()
{
	ifstream fin ("secv3.in");
	fin>>n>>l>>u;
	for(int i=1;i<=n;++i)
		fin>>c[i], c[i]*=100;
	for(int i=1;i<=n;++i)
		fin>>t[i];
}

int f (int K)
{
	for (int i=1;i<=n;++i)
		v[i]=v[i-1]+(long long)c[i]-K*t[i];
	int st=1, dr=1;
	long long smax=-2000000000;
	dq[1]=0;
	for(int i=l;i<=n;++i)
	{
		if (v[i]-v[dq[st]]>smax && i-dq[st]>=l)
			smax=v[i]-v[dq[st]];
		while (v[i]<=v[dq[dr]] && dr>=st)--dr;
		dq[++dr]=i;
		if (i-dq[st]>=u)
			++st;
	}
	if (smax<0)
		return 0;
	return 1;
}
		

void cauta (int st, int dr)
{
	if (st==dr)
	{
		if (sol<st && f(st))
			sol=st;
		return;
	}
	int mij=(st+dr)/2;
	if (!f(mij))
		cauta(st, mij);
	else
	{
		if (mij>sol)sol=mij;
		cauta(mij+1, dr);
	}
}

int main ()
{
	read ();
	cauta (0, 100001);
	freopen("secv3.out", "w", stdout);
	printf("%.2lf", sol/100.);
	return 0;
}