Pagini recente » Cod sursa (job #3131600) | Cod sursa (job #2478904) | Cod sursa (job #542705) | Cod sursa (job #439297) | Cod sursa (job #439298)
Cod sursa(job #439298)
#include <stdio.h>
#include <stdlib.h>
#define FILEIN "gutui.in"
#define FILEOUT "gutui.out"
#define INFINIT 4294967295
#define NMAX 100002
#define byte unsigned char
typedef struct gutuie {
int g, h;
gutuie *next;
} gutuie;
int min(int a, int b) {
if (a<b) return a;
return b;
}
int insert(byte viz[NMAX], gutuie *gutui, int h, int u, int n) {
int nivel_dorit = min(n,(h-gutui->h)/u);
while (viz[nivel_dorit]) {
nivel_dorit--;
if (nivel_dorit<0) return 0;
}
viz[nivel_dorit] = 1;
return 1;
}
int comparator(const void * a, const void * b) {
return -1*(((gutuie*)a)->g - ((gutuie*)b)->g);
}
int main() {
FILE *fin = fopen(FILEIN, "r"), *fout = fopen(FILEOUT, "w");
int n, h, u, i;
long int totalsum = 0;
gutuie gutui[NMAX];
byte viz[NMAX];
//citim datele intr-o lista de gutui
fscanf(fin, "%d %d %d", &n, &h, &u);
for (i=0; i<n; i++) {
fscanf(fin, "%d %d", &gutui[i].h, &gutui[i].g);
viz[i] = 0;
}
viz[n] = 0;
//sfarsit citit date
//sortam datele
qsort(gutui, n, sizeof(gutuie), comparator);
//luam gutuile in ordinea descrescatoare a greutatii
for (i=0; i<n; i++)
//vedem daca putem pune gutuia maxima in lista
if (insert(viz, &gutui[i], h, u, n))
totalsum += gutui[i].g;
fprintf(fout, "%ld\n", totalsum);
fclose(fin);
fclose(fout);
return 0;
}