Pagini recente » Cod sursa (job #2112905) | Cod sursa (job #111003) | Cod sursa (job #1408301) | Cod sursa (job #2082882) | Cod sursa (job #197102)
Cod sursa(job #197102)
#include<stdio.h>
#define nmax 30024
#define Xmax 30024
int c[nmax],t[nmax];
float v[nmax];
float sum[nmax];
int h[nmax],poz[nmax];
int N,L,U;
void change(int a,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 a1,a2;
int i;
for(i=1; i<=N; ++i)
scanf("%d",&c[i]);
for(i=1; i<=N; ++i)
scanf("%d",&t[i]);
float left=0,right=Xmax;
float mij;
int inc,sf;
float 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];
}
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.2f\n",mij);
return 0;
}