Cod sursa(job #509580)

Utilizator bora_marianBora marian bora_marian Data 11 decembrie 2010 13:45:39
Problema Secventa 3 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
# include <fstream>
using namespace std;
int n, l, u, c[30003], t[30003], dq[30003], sol;
long long v[30003];
int verifica (int rez);
void solve (int st, int dr);
int main ()
{
	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];
	solve (0, 100001);
	freopen("secv3.out", "w", stdout);
	printf("%.2lf", sol/100.);
	return 0;
}
int verifica (int rez)
{
	for (int i=1;i<=n;++i)
		v[i]=v[i-1]+(long long)c[i]-rez*t[i];
	int st=1, dr=1;
	long long suma=v[l];
	dq[1]=0;
	for(int i=l;i<=n;++i)
	{
		while (v[i-l]<=v[dq[dr]] && dr>=st)--dr;
		dq[++dr]=i-l;
		if (v[i]-v[dq[st]]>suma)
			suma=v[i]-v[dq[st]];
		while (i-dq[st]>=u)
			++st;
	}
	if (suma>0)
		return 1;
	return 0;
}
void solve (int st, int dr)
{
	if (st==dr)
	{
		if (sol<st && verifica(st))
			sol=st;
		return;
	}
	int mij=(st+dr)/2;
	if (!verifica(mij))
		solve(st, mij);
	else
	{
		sol=mij;
		solve(mij+1, dr);
	}
}