Cod sursa(job #602134)

Utilizator niculina281Soare Oana niculina281 Data 9 iulie 2011 12:13:17
Problema Lupul Urias si Rau Scor 28
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>
int s=0,no=0,h[100010],m[100010][100];
void down(int k)
{
int aux,fiu;
do
	{
	fiu=0;
	if(2*k<=no)
		fiu=2*k;
	if(2*k+1<=no && h[2*k+1]>h[fiu])
		fiu=2*k+1;
	if(h[fiu]>h[k])
		{
		aux=h[k];
		h[k]=h[fiu];
		h[fiu]=aux;
		k=fiu;
		}
	else
		fiu=0;
	}while(fiu!=0);
}
//////////////
void ord()
{
int i;
for(i=no/2;i>=1;i--)
	down(i);		
}
//////////////
void pop()
{
s=s+h[1];
h[1]=h[no--];
down(1);
}
//////////////
int main()
{
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int aux,j,i,n,x,l,a,min=2000000000,b;
scanf("%d%d%d",&n,&x,&l);
for(i=1;i<=n;i++)
	{
	scanf("%d%d",&a,&b);
	aux=a/l;
	if(aux*l<a)
		m[++m[0][aux+1]][aux+1]=b;
	else
		m[++m[0][aux]][aux]=b;
	if(aux<min)
		min=aux;
	}
a=(x-min)/l+1;
for(j=min/l;j<a;j++)
	{for(i=1;i<=m[0][j];i++)
		h[++no]=m[i][j];
	ord();
	pop();
	}	
printf("%d",s);
return 0;
}