Cod sursa(job #436436)
#include<stdio.h>
#include<stdlib.h>
typedef struct fruct{
unsigned int ht;
unsigned int wt;
} fruct;
long h;
int compare ( const void * a, const void * b){
fruct f1, f2;
f1 = *(fruct*)a;
f2 = *(fruct*)b;
return ((h*f1.ht)/f1.wt-(h*f2.wt)/f2.wt);
}
int main (){
FILE * fin = fopen ( "gutui.in", "r");
FILE * fout = fopen ( "gutui.out", "w");
long n, u;
int i;
fruct vec[100000];
fscanf( fin, "%ld", &n);
fscanf( fin, "%ld", &h);
fscanf( fin, "%ld", &u);
for ( i=0; i<n; i++ ){
fscanf (fin, "%d%d", &vec[i].ht, &vec[i].wt);
}
i=0;
unsigned int prada = 0, found;
int gata =0, j;
while ( (h>=0) && (gata==0) ){
qsort(vec, n, sizeof(fruct), compare);
found=0;
while ( (found==0) && (i<n) ){
if ( vec[i].ht<=h ){
j=i;
/*while ( vec[i].ht==vec[j].ht ){
if ( vec[j].wt>vec[i].wt ){
aux=vec[i].wt;
vec[i].wt=vec[j].wt;
vec[j].wt=aux;
}
j++;
}*/
found=1;
}
i++;
}
if ( found==1 ){
prada = prada + vec[i-1].wt;
h = h-u;
}
else
gata=1;
}
fprintf (fout,"%d\n", prada);
fclose ( fin );
fclose ( fout );
return 0;
}