Pagini recente » Cod sursa (job #1101989) | Cod sursa (job #3209248) | Cod sursa (job #1437509) | Cod sursa (job #463188) | Cod sursa (job #463023)
Cod sursa(job #463023)
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int inaltime;
int greutate;
}gutui;
///functie comparare pentru qsort
int compare (const void *a, const void *b){
gutui *item1 = (gutui*)a;
gutui *item2 = (gutui*)b;
return -(item1->greutate - item2->greutate);
}
int main(){
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
int n,h,u;
int i,j,maxim,min=0;
int total=0;
fscanf(fin,"%d %d %d",&n,&h,&u);
gutui *v=(gutui*)malloc(n*sizeof(gutui));
int *level=(int*)malloc((h/u+2)*sizeof(int));
for (i=1;i<=h/u+1;i++)
level[i]=i;
for (i=0;i<n;i++){
fscanf(fin,"%d %d",&v[i].inaltime,&v[i].greutate);
if (i==0)
min=v[i].inaltime;
else if (min>v[i].inaltime)
min=v[i].inaltime;
}
///sortare descrescatoare dupa greutate
qsort(v,n,sizeof(gutui),compare);
maxim=(h-min)/u+1;///numarul maxim posibil de nivele
///descoperirea solutiei (pentru explicatie se consulta readme)
for (i=0;i<n;i++){
if (level[(h-v[i].inaltime)/u+1]>0 && v[i].inaltime<=h){
total+=v[i].greutate;
min=level[(h-v[i].inaltime)/u+1];
for (j=maxim;j>=1;j--)
if (level[j]>=min && level[j]>0)
level[j]--;
else if (level[j]>0)
break;
}
}
fprintf(fout,"%d",total);///solutia finala
fclose(fin);
fclose(fout);
free(v);
free(level);
return 0;
}