Pagini recente » Cod sursa (job #1943467) | Rating Negacevschi Vladimir-Alexandru (vladnega) | Cod sursa (job #174715) | Cod sursa (job #1991597) | Cod sursa (job #441362)
Cod sursa(job #441362)
#include <stdio.h>
#include <stdlib.h>
typedef struct
{
unsigned int niv,kg;
}GUTUIE;
int comp(const void *a,const void *b)
{
unsigned int h1=((GUTUIE*)a)->niv;
unsigned int h2=((GUTUIE*)b)->niv;
if(h1==h2)
{
unsigned int kg1=((GUTUIE*)a)->kg;
unsigned int kg2=((GUTUIE*)a)->kg;
return kg2-kg1;
}
return h2-h1;
}
void updateIns(unsigned int heap[],int index)
{
int root=(index-1)/2;
if(heap[root]>heap[index])
{
unsigned int aux;
aux=heap[root];
heap[root]=heap[index];
heap[index]=aux;
updateIns(heap,root);
}
}
void hIns(unsigned int heap[],int *dim,int val)
{
heap[(*dim)]=val;
updateIns(heap,(*dim));
(*dim)++;
}
void updateRem(unsigned int heap[],int dim,int root)
{
int lNode=root*2+1,rNode=root*2+2,minNode=root;
if(lNode<dim&&heap[lNode]<heap[minNode])
minNode=lNode;
if(lNode<dim&&heap[rNode]<heap[minNode])
minNode=rNode;
if(minNode!=root)
{
unsigned int aux=heap[minNode];
heap[minNode]=heap[root];
heap[root]=aux;
updateRem(heap,dim,minNode);
}
}
void hRem(unsigned int heap[],int *dim)
{
(*dim)--;
heap[0]=heap[(*dim)];
updateRem(heap,*dim,0);
}
int main()
{
freopen("gutui.in","r",stdin);
freopen("gutui.out","w",stdout);
int i,dim=0,sol=0;
unsigned int N,H,U,heap[100000];
GUTUIE vgutui[100000];
scanf("%d %d %d",&N,&H,&U);
H/=U;
for(i=0;i<N;i++)
{
scanf("%d %d",&(vgutui[i].niv),&(vgutui[i].kg));
vgutui[i].niv=(vgutui[i].niv-1)/U;
}
qsort(vgutui,N,sizeof(GUTUIE),comp);
for(i=0;i<N;i++)
if(vgutui[i].niv<=H)
{
hIns(heap,&dim,vgutui[i].kg);
H--;
//H-=U;
break;
}
i++;
for(;i<N;i++)
if(vgutui[i].niv>H)
{
if(vgutui[i].kg>heap[0])
{
hRem(heap,&dim);
hIns(heap,&dim,vgutui[i].kg);
}
}
else
{
hIns(heap,&dim,vgutui[i].kg);
//H-=U;
H--;
}
for(i=0;i<dim;i++)
sol+=heap[i];
printf("%d",sol);
return 0;
}