Pagini recente » Cod sursa (job #32182) | Cod sursa (job #3217387) | Cod sursa (job #3229598) | Cod sursa (job #3250594) | Cod sursa (job #27733)
Cod sursa(job #27733)
#include<stdio.h>
#define infi 1005000
#define nmax 30005
#define valmax 1001
int long n,a1[nmax], u,l,a[nmax],b[nmax],sol;
void citire();void afisare();
void scade(int long k)
{int long i;
for(i=1;i<=n;i++)
a1[i]=a[i]-b[i]*k;
}
int det_max()
{int long i,inc,max=-infi,coada=0,s=0,nr[nmax];
nr[0]=0;
for(i=1;i<=u;i++)
s+=a1[i];
max=s,coada=0,inc=1;
for(i=u+1;i<=n;i++)
{nr[++nr[0]]=i-u;
coada+=a1[i-u];
s-=a1[i-u];s+=a1[i];
if(nr[inc]==i-l)
{coada-=a1[i-l];
inc++;
}
if(coada<0)
{coada=0;
inc=nr[0]+1;
}
if(s+coada>max)
max=s+coada;
}
if(max>0)
return 1;
if(max==0)
return 0;
return -1;
}
void binar()
{int long r,ls=0,ld=valmax*100,mij;
while(ld>ls)
{mij=(ld+ls)/2;
scade(mij);
r=det_max();//det_max() returneaza 0 daca e gata -1 daca e mai mic si 1 daca e mai mare
if(r==0)
{sol=mij;return;}
else
if(r<0)
ld=mij-1;
else
ls=mij+1;
}
//sol=mij;
sol=ld+1;
}
int main()
{citire();
binar();
afisare();
return 0;
}
void afisare()
{
freopen("secv3.out","w",stdout);
if(sol%100<10)
printf("%ld.0%ld",sol/100,sol%100);
else
printf("%ld.%ld",sol/100,sol%100);
}
void citire()
{int long i;
freopen("secv3.in","r",stdin);
scanf("%ld%ld%ld",&n,&u,&l);
for(i=1;i<=n;i++)
{scanf("%ld",&a[i]);
a[i]*=100;
}
for(i=1;i<=n;i++)
{scanf("%ld",&b[i]);
//b[i]*=100;
}
}