Cod sursa(job #499710)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 10 noiembrie 2010 18:06:06
Problema Minim2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#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;
}