Pagini recente » Cod sursa (job #634865) | Cod sursa (job #440372)
Cod sursa(job #440372)
#include <stdio.h>
#include <stdlib.h>
/*typedef struct{
int inaltime;
int greutate;
int index;
}gutui;*/
///functie comparare pentru qsort
/*int compare (const void *a, const void *b){
gutui *item1 = (gutui*)a;
gutui *item2 = (gutui*)b;
return -(item1->greutate - item2->greutate);
}
int compare1 (const void *a, const void *b){
gutui *item1 = (gutui*)a;
gutui *item2 = (gutui*)b;
return (item1->inaltime - item2->inaltime);
}*/
int compare(const void *a,const void *b){
return -(*(int*)a - *(int*)b);
}
int main(){
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
int n,h,u;
int i,j,k,inaltime,greutate;
int total=0;
int prim,secund,nr,nivel_prim,nivel_secund;
fscanf(fin,"%d %d %d",&n,&h,&u);
int **mat;
mat=(int**)malloc((n+2)*sizeof(int*));
for (i=0;i<=n+1;i++)
mat[i]=(int*)malloc((n/2)*sizeof(int));
//gutui *v=(gutui*)malloc(n*sizeof(gutui));
int *v=(int*)malloc((h/u+2)*sizeof(int));
int *aux=(int*)malloc((h/u+3)*sizeof(int));
int *nivel=(int*)malloc((h/u+3)*sizeof(int));
for (i=0;i<h/u+2;i++)
nivel[i]=i;
for (i=0;i<n;i++){
fscanf(fin,"%d %d",&inaltime,&greutate);
mat[(h-inaltime)/u+1][aux[(h-inaltime)/u+1]+1]=greutate;
aux[(h-inaltime)/u+1]++;
}
nr=0;
for (i=1;i<=h/u+1;i++){
qsort(mat[i],n/2,sizeof(int),compare);
if (aux[i]>0)
nr++;
}
/*
for (i=0;i<=h/u+1;i++){
for (j=0;j<n;j++)
printf("%d ",mat[i][j]);
printf("\n");
}
printf("\n\n");
for (i=0;i<=h/u+1;i++)
printf("%d ",aux[i]);
printf("\n");
for (i=0;i<=h/u+1;i++)
printf("%d ",v[i]);
printf("\n\n");*/
prim=mat[1][v[1]];
nivel_prim=1;
for (i=2;i<=h/u+1;i++)
if (mat[i][v[i]]>=prim){
secund=prim;
nivel_secund=nivel_prim;
prim=mat[i][v[i]];
nivel_prim=i;
}
while (nr>0){
total+=mat[nivel_prim][v[nivel_prim]];
//printf("greutate = %d nr=%d nivel_prim=%d nivel=%d\n",mat[nivel_prim][v[nivel_prim]],nr,nivel_prim,nivel[nivel_prim]);
k=nivel[nivel_prim];
for (i=1;i<=h/u+1;i++)
if (nivel[i]>=k)
nivel[i]--;
v[nivel_prim]++;
/*if (v[nivel_prim]==nivel[nivel_prim])
nr--;*/
for (i=1;i<=h/u+1;i++)
if ((v[i]>nivel[i] && aux[i]>0)||(v[i]==aux[i] && aux[i]>0)||(nivel[i]==0 && aux[i]>0)){
nr--;
aux[i]=0;
}
/*printf("nivele: ");
for (i=1;i<=h/u+1;i++)
printf("%d ",nivel[i]);
printf("\n");
printf("aux: ");
for (i=1;i<=h/u+1;i++)
printf("%d ",aux[i]);
printf("\n");*/
prim=-1;
for (i=1;i<=h/u+1;i++)
if (aux[i]>0 && v[i]<=nivel[i] && prim<mat[i][v[i]]){
prim=mat[i][v[i]];
nivel_prim=i;
}
}
fprintf(fout,"%d",total);///solutia finala
fclose(fin);
fclose(fout);
//free(v);
//free(nivel);
return 0;
}