Cod sursa(job #431619)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 1 aprilie 2010 11:04:19
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct oaie
{
	int dist,lana,timp;
};
oaie o[1<<20];
int q,n,x,l,d,a,j,tmax;
long long total;
priority_queue<int> H;
bool comp(const oaie &A,const oaie &B)
{
	if(A.timp<B.timp) return false;
	if(A.timp>B.timp) return true;
	if(A.lana>B.lana) return true;
	return false;
}
int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d%d%d",&n,&x,&l);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&d,&a);
		if(d>x)
		{
			--i, --n;
			continue;
		}
		o[i].dist=d;
		o[i].lana=a;
		o[i].timp=(x-d)/l;
		if(o[i].timp>tmax)
			tmax=o[i].timp;
	}
	sort(o+1,o+n+1,comp);
	o[0].timp=o[1].timp;
	q=1;
	o[n+1].timp=-1;
	for(int i=tmax;i>=0;i--)
	{
		if(o[q].timp==i)
		{
			for(;q<=n;q++)
				if(o[q].timp==i)
					H.push(o[q].lana);
				else break;
		}
		total+=(long long)H.top();
		H.pop();
	}
	printf("%lld",total);
	return 0;
}