Pagini recente » Cod sursa (job #3245078) | Cod sursa (job #2572603) | Cod sursa (job #3143878) | Cod sursa (job #2932378) | Cod sursa (job #436785)
Cod sursa(job #436785)
#include <stdio.h>
#include <stdlib.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)->in - ((gutuie*)a)->in );
}
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 min;
i = 0;
while(i < n){
if((g[i].in + rid) <= h){
val += g[i].gr;
adaugate[nad] = g[i].gr;
nad++;
rid += u;
} else{
min = minim(adaugate,nad);
if(g[i].gr > adaugate[min]){
val -= adaugate[min];
val += g[i].gr;
adaugate[min] = g[i].gr;
}
}
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
return 0;
}