Cod sursa(job #596793)

Utilizator alexeiIacob Radu alexei Data 19 iunie 2011 19:54:38
Problema Secventa 3 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include<stdio.h>
#include<deque>
using namespace std;

#define NMAX 30010

int C[NMAX],T[NMAX];
double B[NMAX],S[NMAX];

/*
	Elimin elementele redundante din deque
*/
void deque_cleanup( deque < int > &D, double val )
{
	while( !D.empty() && D.front() < val )
		D.pop_front();
	while( !D.empty() && D.back() < val )
		D.pop_back();
}

void deque_min_insert( deque < int > &D, int val, double *S )
{
	while( !D.empty() && S[ D.back() ] < S[val] )
		D.pop_back();
	D.push_back( val );
}

inline double deque_best( deque < int > &D, double *S )
{
	return S[ D.front() ];
} 

int main()
{
	if( freopen("secv3.in","r",stdin) == NULL )
		return 1;
	if( freopen("secv3.out","w",stdout) == NULL )
		return 1;

	int L,U,N;	
	
	if( scanf("%d%d%d",&N,&L,&U)!=3 )
		return 1;
	
	int i;

	for(i=1; i<=N; ++i)
		if( scanf("%d",&C[i])!=1 )
			return 1;
			
	for(i=1; i<=N; ++i)
		if( scanf("%d",&T[i])!=1 )
			return 1;
		
	double M=0,eps=0.001;
	double inc=eps,sf=1000;
	double ans=1001;
	
	while( sf-inc > eps )
	{
			/*
				Caut binar solutia
			*/	
			
			// printf("inc %lf sf %lf M %lf\n",inc,sf,M);
			
			M=(inc+sf)/2;
			
			/*
			   Am fixat solutia M. Cu ajutorul acesteia construiesc
			   sirul auxiliar B(i).
			*/
			
			deque< int > Deq;
			
			//printf("Showing S\n");
			
			for( i=1; i<=N; ++i )
			{
				B[i]=(double)( C[i]-M*T[i] );
				S[i]= B[i]+S[i-1];
				
			//	printf(" %lf ",S[i]); 
			}
			
			//printf("\n");
			
			deque_min_insert( Deq, 1, S );
			ans=S[L];
			//printf("L %d ans %lf  Deq %d\n",L,ans,Deq.front());
			
			for( i=L+1; i<=N; ++i )
			{
				deque_cleanup( Deq, i-U+1 );
				deque_min_insert( Deq, i-L , S);
				
			//	printf("Deq.front  %d\n",Deq.front());
				
				double best=S[i]-deque_best( Deq, S );
				if( ans<best )
					ans=best;			
				
			//	printf("( i %d ans %lf \n",i,ans);
			
			}
			
			//printf("M %lf ans %lf\n",M,ans);
			
			if( !ans ) 
				break;
			
			if( ans > 0 )
				inc=M+eps;
			else
				sf=M-eps;	
	}

	printf("%.02lf\n",M);

	return 0;
}