Pagini recente » Cod sursa (job #2806836) | Cod sursa (job #1562321) | Cod sursa (job #900907) | Cod sursa (job #1121891) | Cod sursa (job #440030)
Cod sursa(job #440030)
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int inaltime;
int greutate;
int index;
}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 compare1 (const void *a, const void *b){
gutui *item1 = (gutui*)a;
gutui *item2 = (gutui*)b;
return (item1->inaltime - item2->inaltime);
}
int main(){
FILE *fin=fopen("gutui.in","r");
FILE *fout=fopen("gutui.out","w");
int n,h,u;
int i,j,k;
int total=0;
fscanf(fin,"%d %d %d",&n,&h,&u);
gutui *v=(gutui*)malloc(n*sizeof(gutui));
gutui *aux=(gutui*)malloc(n*sizeof(gutui));
int *nivel=(int*)malloc(n*sizeof(int));
for (i=0;i<n;i++){
fscanf(fin,"%d %d",&v[i].inaltime,&v[i].greutate);
v[i].index=i;
aux[i].inaltime=v[i].inaltime;
aux[i].greutate=v[i].greutate;
aux[i].index=i;
}
qsort(aux,n,sizeof(gutui),compare1);
qsort(v,n,sizeof(gutui),compare);
///impartirea pe nivele a gutuilor
for (i=0;i<n;i++)
if (v[i].inaltime<=h)
nivel[v[i].index]=(h-v[i].inaltime)/u+1;
/*for (i=0;i<n;i++)
printf("dupa inaltime %d %d %d %d\n",aux[i].inaltime,aux[i].index,aux[i].greutate,nivel[aux[i].index]);
printf("\n\n");
for (i=0;i<n;i++)
printf("dupa greutate %d %d %d %d\n",v[i].greutate,v[i].index,v[i].inaltime,nivel[v[i].index]);*/
/*for (i=0;i<n;i++)
printf("%d %d\n",v[i].inaltime,v[i].index);*/
/*for (i=0;i<n;i++)
printf("%d %d\n",nivel[v[i].index],v[i].inaltime);*/
///descoperirea solutiei (pentru explicatie se consulta readme)
for (i=0;i<n;i++){
if (nivel[v[i].index]>0 && v[i].inaltime<=h){
//printf("greutate=%d index=%d\n",v[i].greutate,v[i].index);
total+=v[i].greutate;
j=-1;
k=nivel[v[i].index];
while(1){
j++;
if (nivel[aux[j].index] < k || j>=n)
break;
//printf("%d %d\n",j,aux[j].index);
if (nivel[aux[j].index]>0)
nivel[aux[j].index]--;
}
/*printf("\nnivele:\n");
for (j=0;j<n;j++)
printf("%d %d %d\n",aux[j].inaltime,aux[j].index,nivel[aux[j].index]);
printf("end nivele\n");
printf("\n\n");*/
}
}
fprintf(fout,"%d",total);///solutia finala
fclose(fin);
fclose(fout);
free(v);
free(nivel);
return 0;
}