Pagini recente » Cod sursa (job #2278759) | Cod sursa (job #352975) | Cod sursa (job #1691576) | Cod sursa (job #2828016) | Cod sursa (job #499710)
Cod sursa(job #499710)
#include<stdio.h>
#include<stdlib.h>
#define NM 100001
#define eps 0.0000001
double w[NM];
int m;
inline int tata(int k){return k/2;}
inline int fiu_st(int k){return 2*k;}
inline int fiu_dr(int k){return 2*k+1;}
inline double max(){return w[1];}
void shift_down(int k){
int fiu;
double aux;
do{
fiu=0;
if(fiu_st(k)<=m) fiu=fiu_st(k);
if(fiu_dr(k)<=m&&w[fiu_dr(k)]>w[fiu])
fiu=fiu_dr(k);
if(w[fiu]<=w[k]) fiu=0;
if(fiu){aux=w[fiu];w[fiu]=w[k];w[k]=aux;k=fiu;}
}while(fiu);
}
void shift_up(int k){
double x=w[k];
while(k>1&&w[tata(k)]<x){
w[k]=w[tata(k)];
k=tata(k);
}
w[k]=x;
}
void insert(double x){
m++;w[m]=x;
shift_up(m);
}
void clear(){
w[1]=w[m--];
shift_down(1);
}
int fcmp(const void*x, const void *y){
return *((int*)y)-*((int*)x);
}
int main(){
freopen("minim2.in","r",stdin);
freopen("minim2.out","w",stdout);
int i,j,k,n,nr=0;
int v[NM]={0};
double s=0,a,b,c,p1,p2,t,d1,d2;
scanf("%d",&n);
for(i=0;i<n;++i) scanf("%d",&v[i]),s+=v[i];
scanf("%lf%lf%lf",&a,&b,&c);
c+=eps;
qsort(v,n,sizeof(v[0]),fcmp);
i=0;nr++;insert(v[i]*a);
s-=v[i]-w[m];i++;
while(s>c){
if(i<n){p1=a*v[i];d1=v[i]-p1;}
else d1=0;
p2=b*max();d2=max()-p2;
if(d1>0&&d1>=d2){
s-=d1;
insert(p1);
i++;
}
else{
s-=d2;
if(p2>eps){
w[1]=p2;
shift_down(1);
}
else{
clear();
}
}
nr++;
}
printf("%d",nr);
return 0;
}