Pagini recente » Cod sursa (job #293037) | Cod sursa (job #861171) | Cod sursa (job #1241827) | Cod sursa (job #2533657) | Cod sursa (job #436167)
Cod sursa(job #436167)
Utilizator |
HighScore skyel |
Data |
8 aprilie 2010 09:58:20 |
Problema |
Gutui |
Scor |
20 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
1.61 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*sizeof(int));
for (i = 0; i < nr; ++i)
{
for ( j = gutui[i].coef ; j >= 0; j--)
if (frei[j] == 0)
{
sum += gutui[j].g;
frei[j] = 1;
break;
}
if (j == -1 && nr < n)
nr++;
}
printf("%d\n",sum);
return 0;
}