Pagini recente » Cod sursa (job #518850) | Cod sursa (job #2785887) | Cod sursa (job #128068) | Cod sursa (job #2040645) | Cod sursa (job #133657)
Cod sursa(job #133657)
//secventa3
#include<stdio.h>
#define maxn 30001
FILE*fin=fopen("secv3.in","r");
FILE*fout=fopen("secv3.out","w");
int cost[maxn],t[maxn],maxx=-1,ind[maxn];
double dec[maxn],sum[maxn];
int l,u,n,start,stop;
int mmx(double x)
{
int st,dr,i,j;
double best=-1000;
sum[0]=0;
for(i=1;i<=n;i++)
sum[i]=sum[i-1]+cost[i]-x*t[i];
st=0;dr=0;dec[st]=0;ind[st]=0;
if(sum[l]>best)
{
best=sum[l];
start=1;stop=l;
}
for(i=l+1;i<=n;i++)
{
if(ind[st]<i-u) st++;
j=dr;
while(j>=st&&sum[i-l]<dec[j]) j--;
dr=j+1;
dec[dr]=sum[i-l];
ind[dr]=i-l;
if(sum[i]-dec[st]>best)
{
best=sum[i]-dec[st];
start=ind[st]+1;
stop=i;
}
}
if(best>0) return 1;
return 0;
}
void cb(double xmin,double xmax)
{
double mij;
while(xmax-xmin>1e-3)
{
mij=(xmin+xmax)/2;
if(mmx(mij)) xmin=mij;
else xmax=mij;
}
fprintf(fout,"%.2f",xmin);
}
int main()
{
double n1=0,n2=0;
int i;
fscanf(fin,"%d%d%d",&n,&l,&u);
for(i=1;i<=n;i++)
{
fscanf(fin,"%d",&cost[i]);
if(maxx<cost[i]) maxx=cost[i];
}
for(i=1;i<=n;i++)
fscanf(fin,"%d",&t[i]);
fclose(fin);
cb(0,maxx);
fclose(fout);
return 0;
}