Pagini recente » Cod sursa (job #901492) | Cod sursa (job #438710)
Cod sursa(job #438710)
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
unsigned int ht;
unsigned int wt;
unsigned int niv;
} fruct;
int compare ( const void * a, const void * b){
fruct f1, f2;
f1 = *(fruct*)a;
f2 = *(fruct*)b;
return f2.wt-f1.wt;
}
int main (){
FILE * fin = fopen ( "gutui.in", "r");
FILE * fout = fopen ( "gutui.out", "w");
long n, u, h;
int i;
fscanf( fin, "%ld", &n);
fscanf( fin, "%ld", &h);
fscanf( fin, "%ld", &u);
fruct* vec=(fruct*)malloc(n*sizeof(fruct));
int nr=0;
for (i = 0; i < n; ++i)
{
scanf("%d %d",&vec[i].ht,&vec[i].wt);
vec[i].niv=(h-vec[i].ht)/u+1;
if (nr < vec[i].niv)
nr = vec[i].niv;
if( vec[i].ht > h )
{
i--;
n--;
}
}
int prada=0;
int j;
qsort(vec, n, sizeof(fruct), compare);
int maxim=vec[0].niv;
for ( i=1; i<n; i++)
if ( vec[i].niv>maxim )
maxim=vec[i].niv;
int *level=(int*)malloc((nr+1)*sizeof(int));
for ( i=1; i<nr+1; i++)
level[i]=-1;
for ( i=0; i<nr; i++)
if (vec[i].ht<h){
if ( level[vec[i].niv]==-1 ){
level[vec[i].niv]=i;
prada=prada+vec[i].wt;
}
else{
for ( j=vec[i].niv-1; j>0; j--)
if ( level[j]==-1){
level[j]=i;
prada=prada+vec[i].wt;
break;
}
if ( j==0 && nr<=n)
nr++;
}
}
fprintf(fout,"%d",prada);
fclose(fin);
fclose(fout);
return 0;
}