Cod sursa(job #640674)

Utilizator balakraz94abcd efgh balakraz94 Data 26 noiembrie 2011 12:01:24
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "lupu.in"
#define outfile "lupu.out"
#define n_max 100005
#define INF 1 << 30
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
#define mkp make_pair
#define pii pair<int,int>
using namespace std;

vector < pii > H(1);

int N, D, L;

int sol;

void sift(int);


void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d %d",&N,&D,&L);
	
	int x,y;
	
	H.reserve(n_max);
	
	for(int i=1;i<=N;i++)
	{
		scanf("%d %d",&x,&y);
		
		H.push_back(mkp(y,x));
	}
	
	fclose(stdin);
}



pii get_max_heap()
{
	pii maxim = H[1];
	
	H[1] = H[N--];
	
	sift(1);
	
	return maxim;
}


int cmp(pii x, pii y)
{
	if(x.first < y.first)
		return 1;
	if(x.first == y.first)
		if(x.second < y.second)
			return 1;
	return 0;
}



void sift(int k)
{
	int son = k, l = ls(k), r =rs(k);
	
	if(l<=N && cmp(H[son],H[l]))
		son = l;
	if(r<=N && cmp(H[son],H[r]))
		son = r;
	if(son!=k)
	{
		swap(H[son], H[k]);
		sift(son);
	}
}



void percolate(int k)
{
	while(k>1 && cmp(H[f(k)],H[k]) )
	{
		swap(H[k], H[f(k)]);
		k = f(k);
	}
}



void build_heap()
{
	for(int i = N/2; i; i--)
		sift(i);
}



void rezolva()
{
	build_heap();
	
	pair < int, int > nodc;
	
	int dist = 0;
	
	while(N)
	{
		nodc = get_max_heap();
		
		if(nodc.second + dist > D)
			continue;
		
		sol += nodc.first;
		dist += L;
	}
}




void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	printf("%d\n",sol);

	fclose(stdout);
}




int main()
{
	citeste();
	rezolva();
	afiseaza();
	
	return 0;
}