Pagini recente » Cod sursa (job #1987629) | Cod sursa (job #439514)
Cod sursa(job #439514)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct { //STRUCTURA GUTUI
long hg;
long gg;
long lg;
} gutui;
long u;
long h;
int mycompare(const void* a, const void* b)
{ //FUNCTIE SORTARE DUPA GREUTATE PT QSORT
gutui* ac=(gutui *)a;
gutui* bc=(gutui *)b;
return ((bc->gg)-(ac->gg));
}
int main()
{
long n,j,i,maxl=0,gmax=0;
FILE *f = fopen("gutui.in","r");
FILE *g = fopen("gutui.out","w");
fscanf(f,"%ld %ld %ld",&n, &h, &u);
gutui *a = (gutui *)calloc(n,sizeof(gutui));
for (i=0; i<n; i++) { //CITIM GUTUILE SI ALFAM NIVELUL MAXIM
fscanf(f,"%ld %ld",&a[i].hg, &a[i].gg);
a[i].lg = (long)((h-(a[i].hg))/u);
if (a[i].lg > maxl) maxl = a[i].lg;
}
qsort (a, n, sizeof(gutui), mycompare); //SORTAM DUPA GREUTATE
long *sched = (long*)calloc(maxl+1, sizeof(long)); //VECTORUL DE SCHEDULE
for (i = 0; i<n; i++)
for (j=a[i].lg; j>=0; j--)
if (sched[j] == 0) {
sched[j] = a[i].gg; //UMPLEM VECOTORUL DE SCHEDULE
break;
}
for (i=0; i<=maxl; i++)
gmax+=sched[i]; //GREUTATEA MAXIMA PE CARE O POATE DUCE GIGEL
fprintf(g,"%ld",gmax);
fclose(g);
//COMPLEXITATE MAXIMA PB -> N*NIVELUL MAXIM
return 0;
}