Pagini recente » Cod sursa (job #1528831) | Cod sursa (job #2635547) | Cod sursa (job #2645520) | Cod sursa (job #312853) | Cod sursa (job #133419)
Cod sursa(job #133419)
//secventa3
#include<stdio.h>
#define maxn 100
FILE*fin=fopen("secv3.in","r");
FILE*fout=fopen("secv3.out","w");
int sum[maxn],cost[maxn],t[maxn],maxx=-1,best,dec[maxn],ind[maxn];
int l,u,n,start,stop;
int mmx(int x)
{
int st,dr,i,j;
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(int xmin,int xmax)
{
int mij;
if(xmin==xmax) if(mmx(xmin)) return ;
else{mmx(xmin-1);return ;}
else
{
mij=(xmin+xmax)>>1;
if(mmx(mij))
cb(mij+1,xmax);
else
cb(xmin,mij-1);
}
}
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);
for(i=start;i<=stop;i++)
{
n1+=cost[i];
n2+=t[i];
}
fprintf(fout,"%.2lf",(n1/n2));
fclose(fout);
return 0;
}