Pagini recente » Cod sursa (job #350733) | Cod sursa (job #1494507) | cnrv_oji_1 | Cod sursa (job #2725108) | Cod sursa (job #438608)
Cod sursa(job #438608)
Utilizator |
HighScore skyel |
Data |
10 aprilie 2010 21:42:42 |
Problema |
Gutui |
Scor |
10 |
Compilator |
cpp |
Status |
done |
Runda |
teme_upb |
Marime |
2.51 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;
}
void swap(int &a, int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}
void add(int *heap,int n,int value)
{
int aux;
heap[n]=value;
aux=n;
while (heap[aux] < heap[aux/2])
{
swap(heap[aux],heap[aux/2]);
aux/=2;
}
}
int min(int a,int b)
{
return a>b?b:a;
}
void del(int *heap, int n,int pos)
{
int aux;
heap[pos]=0;
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;
}
}
int main()
{
int j,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=(int*)calloc(nr+1,sizeof(int));
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);
add(heap,taken,gutui[i].g);
}
}
}
for ( i = 1; i <= taken; ++i)
sum+=heap[i];
printf("%d\n",sum);
return 0;
}