Cod sursa(job #889792)

Utilizator superman_01Avramescu Cristian superman_01 Data 24 februarie 2013 18:17:03
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<cstdio>
#include<deque>

#define MAX 1005
#define nmax 30005

using namespace std;

deque <int> dq;

int n,l,u;
int c[nmax],t[nmax];
	float 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]);
	
}

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(1) ; i <= n ; ++i )

	{
		while(dq.size() && s[ dq.back() ] > s[i])
			dq.pop_back();
		
		dq.push_back(i);
		
		while(i-dq.front() > u-l)
			dq.pop_front();
		
		if(  s[i] - s[dq.front()]   > 0)
			return 1;	
		
	}		
		return 0;
}

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

	while( lo <= hi )
	{
		double mid=lo+(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("%0.4f",result);
}



int main()
{
	read();
	solve();
	write();
	return 0;	
}