Cod sursa(job #325743)

Utilizator nusmaibunkeleviprofesor cicalescu nusmaibunkelevi Data 22 iunie 2009 08:49:56
Problema Lupul Urias si Rau Scor 4
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<stdio.h>
#include<stdlib.h>

#define NM 100001
struct bee{int d,a,g;};
typedef bee*pb;
bee v[NM];
struct oaie{int d,a;};
oaie h[NM];
int n,n1,idgr;

inline int tata(int k){return k/2;}
inline int fiu_st(int k){return k*2;}
inline int fiu_dr(int k){return k*2+1;}
inline int max(){return h[1].a;}

void sift(int k){
int fiu;
oaie aux;
do{
	fiu=0;
	if(fiu_st(k)<=n) fiu=fiu_st(k);
	if(fiu_dr(k)<=n&&h[fiu_dr(k)].a>h[fiu_st(k)].a)
		fiu=fiu_dr(k);
	if(h[fiu].a<=h[k].a) fiu=0;
	if(fiu) aux=h[k],h[k]=h[fiu],h[fiu]=aux,k=fiu;
	}while(fiu);
}
void percolate(int k){
oaie temp=h[k];
while(k>1&&temp.a>h[tata(k)].a) h[k]=h[tata(k)],k=tata(k);
h[k]=temp;
}
void insert(bee x){
++n;
h[n].d=x.d,h[n].a=x.a;
percolate(n);
}
void clear(int k){
h[k]=h[n--];
if(n)
	if(k>1&&h[k].a>h[tata(k)].a) percolate(k);
	else sift(k);
}
/*
void build_heap(){
int i;
for(i=n/2;i;--i) sift(i);
} */

int fcmp(void const*e,void const*f){
return ((pb)e)->g-((pb)f)->g;
}
int main(){
freopen("lupu.in","r",stdin);
freopen("lupu.out","w",stdout);
int i,j,m,x,l,d,a,c,r;
scanf("%d%d%d",&m,&x,&l);
c=x/l,r=x%l;
for(i=1;i<=m;++i){
	scanf("%d%d",&d,&a);
	if(h[i].d<=x)
		{
		v[n1].d=d,v[n1].a=a;
		if(r) v[n1].g=(v[n1].d+r)/l;
		else v[n1].g=(v[n1].d+l-1)/l;
		++n1;
		}
	}
qsort(v,n1,sizeof(v[0]),fcmp);
long long s=0L;
for(i=0;i<n1;++i){
	idgr=v[i].g;j=i;
	while(v[j].g==idgr) n++,insert(v[j]),j++;
	s+=h[1].a;clear(1);
	if(j==n1) break;
	i=j-1;
	}
printf("%lld",s);
return 0;
}