Pagini recente » Cod sursa (job #3275364) | Diferente pentru documentatie/textile intre reviziile 107 si 88 | Monitorul de evaluare | Profil alex.cojocaru | Cod sursa (job #438464)
Cod sursa(job #438464)
# include <stdio.h>
# include <stdlib.h>
# define MAXL 100000
typedef struct gut{
int h; //inaltime
int v; //valoare
int p; //pasul maxim la care poate fi culeasa gutuia
}Gutuie;
int compare(const void* a, const void* b){ //functia de comaprare pentru qsort
Gutuie *aa = (Gutuie*)a;
Gutuie *bb = (Gutuie*)b;
if (aa->p < bb->p)
return -1;
else
if (aa->p > bb->p)
return 1;
else
if (aa->v < bb->v)
return 1;
else
return -1;
}
int main(){
int n, H, U, i, j, sol[MAXL], nsol, pas, s, k, l;
Gutuie g[MAXL];
FILE *fin, *fout;
fin=fopen("gutui.in","r");
fout=fopen("gutui.out","w");
fscanf(fin,"%d%d%d",&n, &H, &U);
for (i=0;i<n;i++){
fscanf(fin,"%d%d",&g[i].h,&g[i].v); //citesc informatiile referitoare la gutuie
g[i].p = (H - g[i].h)/U + 1; //calculez pasul la care poate fi culeasa
}
qsort(g,n,sizeof(Gutuie),*compare); //sortez crescator dupa pas si descrescator dupa valoare
nsol = 0;
for (i=0;i<n;i++){
if (i==0 || g[i].p != g[i-1].p){ //pasul urmator;
pas = g[i].p;
for (j=i;j<n && g[j].p == pas && j-i<pas;j++){//parcurg gutuile de la pasul curent(sunt in ordine descrescatoare;
if (nsol<pas){ //daca pot sa adaug la solutie fara sa elimin gutui culese anterior:
//inserez pe g[j].v in vectorul sol a.i. sa ramana sortat descrescator;
for (k=0;k<nsol;k++)
if (sol[k]<g[j].v)
break;
for (l=nsol;l>k;l--)
sol[l] = sol[l-1];
sol[l] = g[j].v;
nsol++;
}
else{
if (g[j].v > sol[nsol-1]){ //daca cea mai slaba gutuie din solutie e mai slaba decat gutuia curenta:
//elimin ultimul element din sol si inserez pe g[j].v;
for (k=0;k<nsol;k++)
if (sol[k]<g[j].v)
break;
for (l=nsol;l>k;l--)
sol[l] = sol[l-1];
sol[l] = g[j].v;
}
}
}
}
}
s = 0; //calculez suma si o scriu in fisier:
for (i=0;i<nsol;i++){
s+=sol[i];
}
fprintf(fout,"%d\n",s);
fclose(fin);
fclose(fout);
return 0;
}