Cod sursa(job #437832)
#include <stdio.h>
#include <stdlib.h>
typedef struct copac{
int inaltime;
int greutate;
}gutui;
int compare (const void * a, const void * b){
gutui *x, *y;
x = (gutui*)a;
y = (gutui*)b;
return y->greutate - x->greutate;
}
int main(){
FILE *f = fopen("gutui.in", "r");
FILE *g = fopen("gutui.out", "w");
int N; // N = numarul de gutui din pom
fscanf(f, "%d", &N);
int H; // H = inaltimea maxima la care poate ajunge Gigel
fscanf(f, "%d", &H);
int U; // U = cu cat se ridica crengile copacului
fscanf(f, "%d", &U);
int *inaltimi, *greutati;
gutui *pom;
pom = (gutui *) malloc ( N * sizeof(gutui));
int i, j;
for (i = 0; i < N; i++){
fscanf(f, "%d", &pom[i].inaltime);
fscanf(f, "%d", &pom[i].greutate);
}
qsort(pom, N, sizeof(gutui), compare); //aici fac sortarea descrescatoare dupa greutate
//calculez momentul pentru fiecare gutuie
int *moment = (int *) malloc ( N * sizeof(int));
for ( i = 0; i < N; i++ ){
moment[i] = ( H - pom[i].inaltime) / U ;
}
int valabil[N];
for ( i = 0; i < N; i++ ){
valabil[i] = 0;//initial toate momentele sunt accesabile
}
int greutateaCuleasa = 0;
for ( i = 0; i < N; i++ ){
if ( valabil[moment[i]] == 0 ){
valabil[moment[i]] = 1;
greutateaCuleasa += pom[i].greutate;
}
else{
for ( j = moment[i]; j >= 0; j-- ){
if ( valabil[j] == 0 ){
valabil[j] = 1;
greutateaCuleasa += pom[i].greutate;
break;
}
}
}
}
fprintf(g, "%d", greutateaCuleasa);
fclose(f);
fclose(g);
return 0;
}