Pagini recente » Cod sursa (job #289050) | Cod sursa (job #2712431) | Cod sursa (job #1559531) | Cod sursa (job #107031) | Cod sursa (job #438568)
Cod sursa(job #438568)
Utilizator |
HighScore skyel |
Data |
10 aprilie 2010 21:15:50 |
Problema |
Gutui |
Scor |
100 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
1.77 kb |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define in "gutui.in"
#define out "gutui.out"
typedef struct
{
int h;
int g;
int coef;
}pom;
int compare2(const void *a,const void *b)
{
pom *x,*y;
x=(pom*)a;
y=(pom*)b;
return -x->g + y->g ;
}
int compare(const void* a,const void* b)
{
pom *x,*y;
x=(pom*)a;
y=(pom*)b;
if (x->coef != y->coef)
return x->coef-y->coef;
else
return -x->g+y->g;
}
int main()
{
int j,n,i,max_height,up_height,sum=0,nr=0,*frei;
pom *gutui;
freopen(in,"r",stdin);
freopen(out,"w",stdout);
scanf("%d %d %d",&n,&max_height,&up_height);
gutui=(pom*)malloc(n*sizeof(pom));
for (i = 0; i < n; ++i)
{
scanf("%d %d",&gutui[i].h,&gutui[i].g);
gutui[i].coef=(max_height-gutui[i].h)/up_height+1;
if (nr < gutui[i].coef)
nr = gutui[i].coef;
if( gutui[i].h > max_height )
{
i--;
n--;
}
}
qsort(gutui,n,sizeof(pom),compare2);
frei = (int*)malloc(nr*sizeof(int));
memset(frei,0,(nr+1)*sizeof(int));
for (i = 0; i < nr; ++i)
{
for ( j = gutui[i].coef ; j > 0; j--)
{
//printf("%d %d\n",j,frei[j]);
if (frei[j] == 0)
{
// printf("me:%d %d %d \n",gutui[i].h,gutui[i].g,gutui[i].coef);
sum += gutui[i].g;
frei[j] = 1;
break;
}
}
if (j == 0 && nr < n)
nr++;
}
printf("%d\n",sum);
return 0;
}