Pagini recente » Cod sursa (job #406548) | Cod sursa (job #660537) | Cod sursa (job #919910) | Cod sursa (job #1946566) | Cod sursa (job #441676)
Cod sursa(job #441676)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define file_in "gutui.in"
#define file_out "gutui.out"
typedef struct fruit_
{
long int height;
long int weight;
} fruit;
int comp(const void *o1, const void *o2)
{
fruit *a = (fruit *)o1;
fruit *b = (fruit *)o2;
if((*a).weight != (*b).weight)
return (*b).weight - (*a).weight;
else
return (*b).height - (*a).height;
}
int main()
{
fruit *fruits;
long int i, j, k, max, N, H, U, *best;
freopen(file_in, "rt", stdin);
freopen(file_out, "wt", stdout);
scanf("%li %li %li", &N, &H, &U);
fruits = (fruit *)malloc(N*sizeof(fruit));
best = (long int *)malloc(N*sizeof(long int));
for(i = 0; i < N; i++)
scanf("%li %li", &fruits[i].height, &fruits[i].weight);
// VARIANTA 2
qsort(fruits, N, sizeof(fruit), comp);
for(i=0;i<N;i++)
{
max = 0;
for(j=0;j<i;j++)
{
if((fruits[j].height + U <= H)&&(max < best[j]))
max = best[j];
}
best[i] = max + fruits[i].weight;
}
// VARIANTA 1
/*memset(best, 0, N*sizeof(long int));
for(i=0;i<N;i++)
{
max = 0;
for(j=0;j<N;j++)
if((i != j) && (fruits[j].height + U <= H) && (max < best[j]))
max = best[j];
best[i] = max + fruits[i].weight;
}*/
max = 0;
for(i=0;i<N;i++)
if(max < best[i])
max = best[i];
printf("%li\n", max);
free(fruits);
free(best);
fclose(stdin);
fclose(stdout);
return 0;
}