Cod sursa(job #889944)

Utilizator superman_01Avramescu Cristian superman_01 Data 24 februarie 2013 19:29:14
Problema Secventa 3 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<cstdio>
#include<deque>

#define MAX 100005

#define nmax 30005

using namespace std;

deque < int > dq;

int n,l,u;
short int c[nmax],t[nmax];
double result;	

void read( void )
{
	freopen("secv3.in","r",stdin);
	scanf("%d%d%d",&n,&l,&u);
	for(int i(1); i <= n ; ++i )
		scanf("%d",&c[i]);
	for(int i(1); i <= n ; ++i )
		scanf("%d",&t[i]);
	fclose(stdin);
}

bool check ( double m )
{
	
	double s[nmax];
		
	s[0]=0;
	
    dq.clear();
	
	for(int i(1) ; i <= n ; ++i )
		s[i]=s[i-1]+(double)c[i]-m*t[i];
	
	for(int i(l) ; i <= n ; ++i )

	{
		while(!dq.empty() && s[ dq.back() ] >= s[i-l+1])
			dq.pop_back();
		
		dq.push_back( i-l+1 );
		
		while(    i - dq.front() >  u - l )
			dq.pop_front();
		
		if(  s[i] - s[dq.front()]   > 0 )
			return true;	
		
	}		
		return false;
}

void solve ( void )
{
	double lo=0;
	double hi=MAX;

	while( hi-lo > 0.0001 )
	{
		double mid=(hi+lo)/2;
		
		if( check(mid)  )
		{
			result=mid;
			lo=mid+0.0001;
			
		}
		else
		{
			
			hi=mid-0.0001;
			
		}
		
		
		
		
		
	}
	
	
	
}
void write( void )
{
	freopen("secv3.out","w",stdout);
	printf("%.2lf\n",result);
	fclose(stdout);
}



int main()
{
	read();
	if(l!=u)
	solve();
	write();
	return 0;	
}