Pagini recente » Cod sursa (job #1471578) | Cod sursa (job #2460051) | Cod sursa (job #1859440) | Cod sursa (job #2353825) | Cod sursa (job #596793)
Cod sursa(job #596793)
#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;
}