Cod sursa(job #487304)

Utilizator Cristi09Cristi Cristi09 Data 24 septembrie 2010 17:57:47
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<stdio.h>
#include<algorithm>
#define NMAX 100001
using namespace std;
int n, l, x, var, size, heap[NMAX], aux;
long long sol;

struct str
{
	int d,a;
}vec[NMAX];
int cmp(str a,str b)
{
	return (a.d > b.d);
}

int left_son(int x)
{
	return x*2;
}
int right_son(int x)
{
	return x*2+1;
}
int father(int x)
{
	return x/2;
}
void sift(int x)
{
	int son;
	do
	{
		son = 0;
		if(left_son(x)<=size)
		{
			son = left_son(x);
			if(right_son(x)<=size && heap[right_son(x)] > heap[left_son(x)])
			{
				son = right_son(x);
			}
			if(heap[son] < heap[x])
				son = 0;
		}
		if(son)
		{
			aux = heap[son];
			heap[son] = heap[x];
			heap[x] = aux;
			x = son;
		}
	}while(son);
}
void percolate(int x)
{
	
	while(father(x) > 0 && heap[father(x)] < heap[x])
	{
		aux = heap[x];
		heap[x] = heap[father(x)];
		heap[father(x)] = aux;
		x = father(x);
	}
}
void insert(int x)
{
	heap[++size] = x;
	//heap[size].d = pas;
	percolate(size);
}
void cut(int x)
{
	heap[x] = heap[size];
	heap[size--] = 0;
	
	if(father(x)>0 && heap[father(x)] < heap[x])
	percolate(x);
	else sift(x);
}
int main()
{
	FILE*f = fopen("lupu.in","r");
	fscanf(f,"%d %d %d",&n,&x,&l);
	int i = 1;
	for(;i<=n;++i)
	{
		fscanf(f,"%d %d",&vec[i].d,&vec[i].a);
		vec[i].d = (x - vec[i].d)/l+1;
		if(vec[i].d == 0)printf("%d ",i);
	}
	fclose(f);
	
	sort(vec+1, vec+n+1, cmp);
	
	int cont;
	
	for( i = vec[1].d, cont = 1; i>=1 && cont<=n;--i)
	{
		while(vec[cont].d == i && cont<=n)
		{
			insert(vec[cont++].a);
		}
		if(size)
		{
			sol += heap[1];
			cut(1);
		}
	}
	
	FILE*g = fopen("lupu.out","w");
	fprintf(g,"%lld\n",sol);
	/*for(i = 1;i<=n;++i)
		fprintf(g,"%d ",vec[i].d);
	fprintf(g,"\n");
	for(i=1;i<=n;++i)
		fprintf(g,"%d ",vec[i].a);*/
	fclose(g);
	
	return 0;
}