Pagini recente » Cod sursa (job #105223) | Cod sursa (job #1589218) | Cod sursa (job #606802) | Cod sursa (job #985059) | Cod sursa (job #436772)
Cod sursa(job #436772)
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
#define NMAX 100000
typedef struct gutuie{
int in; // inaltime
int gr; // greutate
int ales;
} gutuie;
int compare (const void * a, const void * b)
{
//return ( ((gutuie*)b)->gr/((gutuie*)b)->in - ((gutuie*)a)->gr/((gutuie*)a)->in );
return ( ((gutuie*)b)->in - ((gutuie*)a)->in );
}
int compare2 (const void * a, const void * b)
{
return ( *(int*)b - *(int*)a );
}
int minim(int v[], int n){
int i;
int min = 0;
for(i = 1; i < n; i++){
if(v[i] < v[min])
min = i;
}
return min;
}
int alegere(gutuie g[NMAX], int n, int h, int u){
int rid = 0;; // ridicare curenta
int i;
int val = 0;
int adaugate[NMAX];
int nad = 0;
//int trebuieSortat;
int min;
// treaba serioasa
i = 0;
while(i < n){
if((g[i].in + rid) <= h){
val += g[i].gr;
adaugate[nad] = g[i].gr;
nad++;
rid += u;
//trebuieSortat = 1;
} else{
//if(trebuieSortat){
// qsort (adaugate, nad, sizeof(int), compare2);
// trebuieSortat = 0;
//}
min = minim(adaugate,nad);
if(g[i].gr > adaugate[min]){
val -= adaugate[min];
val += g[i].gr;
adaugate[min] = g[i].gr;
//trebuieSortat = 1;
}
}
i++;
}
//
return val;
}
int main(){
FILE* f;
int n, h, u;
gutuie g[NMAX];
int i;
int rez;
// citire
f = fopen("gutui.in","r");
fscanf(f,"%d %d %d",&n,&h,&u);
for(i = 0; i < n; i++){
fscanf(f,"%d %d", &g[i].in, &g[i].gr);
g[i].ales = 0;
}
fclose(f);
// aflare valoare
qsort (g, n, sizeof(gutuie), compare);
rez = alegere(g,n,h,u);
// debugging
printf("%d %d %d\n",n,h,u);
for(i = 0; i < n; i++)
printf("%d %d\n",g[i].in, g[i].gr);
printf("solutia: %d",rez);
// scriere
f = fopen("gutui.out","w");
fprintf(f,"%d",rez);
fclose(f);
// terminare
// getch();
return 0;
}