Pagini recente » Cod sursa (job #683916) | Cod sursa (job #60073) | Cod sursa (job #2825759) | Cod sursa (job #1914477) | Cod sursa (job #438653)
Cod sursa(job #438653)
Utilizator |
HighScore skyel |
Data |
10 aprilie 2010 22:25:50 |
Problema |
Gutui |
Scor |
20 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
2.92 kb |
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 0xffffffff
#define in "gutui.in"
#define out "gutui.out"
typedef struct
{
unsigned h;
unsigned g;
unsigned 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;
}
void swap(unsigned &a, unsigned &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
void add(unsigned *heap,unsigned n,unsigned value)
{
int aux;
heap[n]=value;
aux=n;
while (heap[aux] < heap[aux/2] && aux > 1)
{
swap(heap[aux],heap[aux/2]);
aux/=2;
}
}
void del(unsigned *heap, unsigned n,unsigned pos)
{
heap[pos]=heap[n];
while (n >= pos)
{
if (heap[pos*2] < heap[pos*2+1])
{
swap(heap[pos*2],heap[pos]);
pos*=2;
}
else
{
swap(heap[pos*2+1],heap[pos]);
pos=pos*2+1;
}
}
}
void print(unsigned * heap,unsigned n)
{
unsigned i;
for (i=1;i<=n+1;++i)
printf("%d ",heap[i]);
printf("\n");
}
int main()
{
unsigned n,i,max_height,up_height,taken,sum=0,nr=0,*heap;
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--;
}
}
heap=(unsigned*)calloc(n,sizeof(unsigned));
for (i = 0;i < n; ++i)
heap[i]=INF;
qsort(gutui,n,sizeof(pom),compare);
taken=0;
for ( i = 0; i < n; ++i)
{
if (taken < gutui[i].coef)
{
taken++;
add(heap,taken,gutui[i].g);
}
else
{
if (gutui[i].g > heap[1])
{
del(heap,taken,1);
//printf("x");
//print(heap,taken);
add(heap,taken,gutui[i].g);
}
}
//print(heap,taken);
}
for ( i = 1; i <= taken; ++i)
{
if (heap[i]!=INF)
sum+=heap[i];
}
printf("%u\n",sum);
return 0;
}