Pagini recente » Borderou de evaluare (job #122457) | Borderou de evaluare (job #2160225) | Cod sursa (job #436699)
Cod sursa(job #436699)
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
//using namespace std;
int n,h,u;
typedef struct {
unsigned int height;
unsigned int weight;
unsigned int clas;
}gutuie;
gutuie *vect;
int my_compare(const void *a,const void *b){
gutuie *unu=(gutuie *) a;
gutuie *doi=(gutuie *) b;
return (doi->weight-unu->weight);
}
int comp(const void * aa,const void * bb)
{ int *a=(int *) aa;
int *b=(int *) bb;
if (*a==*b)
return 0;
else
if (*a < *b)
return -1;
else
return 1;
}
int main(){
int i,j,max_dif=0,k=0;
int *solutie;
// short *cules;
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
fscanf(fin,"%d",&n);
fgetc(fin);
fscanf(fin,"%d",&h);
fgetc(fin);
fscanf(fin,"%d",&u);
//respect restrictile
if(n<1||n>100000)
return 1;
vect=(gutuie *)malloc(n*sizeof(gutuie));
//cules=(short *)calloc(n,sizeof(short));
for(i=0;i<n;i++){
fgetc(fin);
fscanf(fin,"%d",&vect[i].height);
fgetc(fin);
fscanf(fin,"%d",&vect[i].weight);
vect[i].clas=(h-vect[i].height)/u+1;
if(vect[i].clas>max_dif)
max_dif=vect[i].clas;
}
solutie=(int *)calloc(max_dif+1,sizeof(int));
// cules=(short *)calloc(max_dif+1,sizeof(short));
qsort(vect,n,sizeof(gutuie),my_compare);
/*for(i=0;i<n;i++)
printf("\n%d %d %d %d ",vect[i].height,vect[i].weight,vect[i].clas,max_dif);
*/
i=0;
int nrgutui=0;
for(i=0;i<n && nrgutui<=max_dif;i++){
k=vect[i].clas;
if(solutie[k]==0){
solutie[k]=vect[i].weight;
nrgutui++;
}
else
for(j=k-1;j>=0;j--)
if(solutie[j]==0){
solutie[j]=vect[i].weight;
nrgutui++;
break;
}
}
/*
metoda pe care am abordat-o prima data
dar care era prea lenta datorita qsortului de mai jos
in teorie si ea functioneaza
while(i<n){
k=vect[i].clas;
for( g=depl ; g < k && i < n; g++)
solutie[depl++]=vect[i++].weight;
schimb=0;
qsort(solutie,depl,sizeof(int),comp);
for(g=i;vect[g].clas==k&&schimb<k;g++)
for(j=0;j<depl&&schimb<k;j++)
if(solutie[j]<vect[g].weight) {
solutie[j]=vect[g].weight;
schimb++;
break;
}
i=g;
}
*/
int sum=0;
for(i=1;i<=max_dif;i++){
sum+=solutie[i];
//printf("%d ",solutie[i]);
}
fprintf(fout,"%d",sum);
// getch();
return 0;
}