Pagini recente » Cod sursa (job #1659405) | Cod sursa (job #2146254) | Cod sursa (job #157128) | Cod sursa (job #663428) | Cod sursa (job #197238)
Cod sursa(job #197238)
#include<stdio.h>
#define nmax 30024
#define Xmax 30000
double c[nmax],t[nmax];
double v[nmax];
double sum[nmax];
int h[nmax],poz[nmax];
int N,L,U;
void change(const int a,const int b)
{
h[a]^=h[b];
h[b]^=h[a];
h[a]^=h[b];
}
void upp(int stuff)
{
int father=stuff>>1,ctrl=stuff;
if( father>=1 )
if( sum[h[father]]<sum[h[stuff]])
ctrl=father;
if( ctrl!=stuff )
{
change(ctrl,stuff);
int aux=poz[h[father]];
poz[h[father]]=poz[h[stuff]];
poz[h[stuff]]=aux;
upp(ctrl);
}
}
void down(int stuff)
{
int left=stuff<<1;
int right=left+1,ctrl=stuff;
if( left<=N )
{
if( sum[ h[left] ]>sum[h[ctrl]] )
ctrl=left;
if( right<=N )
if( sum[h[right]]>sum[h[ctrl]] )
ctrl=right;
if( ctrl!=stuff )
{
change(ctrl,stuff);
poz[ h[ctrl] ]=ctrl;
poz[ h[stuff] ]=stuff;
down(ctrl);
}
}
}
int main()
{
freopen("secv3.in","r",stdin);
freopen("secv3.out","w",stdout);
scanf("%d%d%d",&N,&L,&U);
int i,a1,a2;
for(i=1; i<=N; ++i)
scanf("%lf",&c[i]);
for(i=1; i<=N; ++i)
scanf("%lf",&t[i]);
double left=0,right=Xmax;
double mij;
int inc,sf;
double solt;
while( left<=right )
{
mij=(right+left)/2;
sf=0;
for(i=1; i<=N; ++i){
v[i]=c[i]-t[i]*mij;
sum[i]=sum[i-1]+v[i];
//printf("%f ",sum[i]);
}
//printf("\n");
for(i=L; i<=U && i<=N; ++i){
h[++sf]=i;
poz[i]=sf;
upp(sf);
}
solt=sum[ h[1] ];
a2=N-L+1;
inc=L;
for(i=2; i<=a2; ++i){
poz[ h[sf] ]=poz[inc];
change( poz[inc], sf );
--sf;
down(poz[inc]);
++inc;
if( i+U-1<=N )
{
++sf;
h[sf]=i+U-1;
poz[i+U-1]=sf;
upp(sf);
}
a1=sum[h[1]]-sum[i-1];
if( solt<a1 )
solt=a1;
}
if( solt>0 )
right=mij-1;
if( solt<0 )
left=mij+1;
if( !solt ){
break;
}
}
printf("%0.2lf\n",mij);
return 0;
}