Cod sursa(job #509542)

Utilizator loginLogin Iustin Anca login Data 11 decembrie 2010 11:56:38
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 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=v[l];
	dq[1]=0;
	for(int i=l+1;i<=n;++i)
	{
		if (v[i]-v[dq[st]]>smax)
			smax=v[i]-v[dq[st]];
		while (v[i-l]<=v[dq[dr]] && dr>=st)--dr;
		dq[++dr]=i-l;
		while (i-dq[st]>=u)
			++st;
	}
	if (smax>0)
		return 1;
	return 0;
}
		

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
	{
		sol=mij;
		cauta(mij+1, dr);
	}
}

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