Cod sursa(job #371719)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 6 decembrie 2009 13:21:27
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>
#include <algorithm>
#include <set>
#define N 1<<17
#define pb push_back
using namespace std;
int n,x,l,heap[N],r;
long long rez;
struct oaie
{
	int val,lana;
};
struct timp
{
	int x,c;
};
timp T[N];
oaie v[N];
bool comp(timp a,timp b)
{
	if (a.x>b.x)
		return 1;
	return 0;
}
void read()
{
	scanf("%d%d%d",&n,&x,&l);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d%d",&v[i].val,&v[i].lana);
		if (x<=v[i].val)
		{
			T[i].x=1;
			T[i].c=v[i].lana;
		}
		else
		{
			T[i].x=(x-v[i].val)/l+1;
			T[i].c=v[i].lana;
		}
	}
	sort(T+1,T+n+1,comp);
}
void interschimba(int poz1, int poz2)
{
	int temp = heap[poz1];
	heap[poz1] = heap[poz2];
	heap[poz2] = temp;
}
void mut_in_sus(int poz)
{
	if (poz > 1 && heap[poz/2] < heap[poz]) 
	{
		interschimba(poz, poz/2);
		mut_in_sus(poz/2);
	}
}
void mut_in_jos(int poz)
{
	if ((2*poz  <= r && heap[poz] < heap[2*poz] ) ||
		(2*poz+1<= r && heap[poz] < heap[2*poz+1])) 
		{
			int maximum = 2*poz;
			if (2*poz+1 <= r && heap[2*poz+1] > heap[2*poz]) 
				maximum = 2*poz+1;
			interschimba(poz, maximum);
			mut_in_jos(maximum);
		}
}
void solve()
{
	int valoare=T[1].x,poz=0;
	while (valoare>=1)
	{
		while (T[poz+1].x==valoare)
		{
			poz++;
			heap[++r]=T[poz].c;
			mut_in_sus(r);
		}
		if (r)
		{
			rez+=heap[1];
			heap[1]=heap[r];
			r--;
			mut_in_jos(1);
		}
		valoare--;
	}
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	read();
	solve();
	printf("%lld\n",rez);
	return 0;
}