Cod sursa(job #344713)

Utilizator prdianaProdan Diana prdiana Data 31 august 2009 14:35:00
Problema Lupul Urias si Rau Scor 84
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define MAXN 200002

using namespace std;

vector< vector<int> > v;
priority_queue<int> pq;
struct oaie
{
	int puf,dist;
};

oaie t[MAXN];

int main()
{
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);

	int nro,dmax,dl,i,nrf,tl = 0;
	oaie aux;
	scanf("%d%d%d",&nro,&dmax,&dl);
	for (i=0;i<nro;i++)
	{
		scanf("%d%d",&aux.dist,&aux.puf);
		t[i].dist = (dmax-aux.dist)/dl;
		t[i].puf = aux.puf;
		if (t[i].dist>tl)
		{
			tl = t[i].dist;
		}
	}
	v.resize(MAXN);
	for (i=0;i<nro;i++)
	{
		if (t[i].dist < 0)
		{
			for (i=9;i>8;);
		}
		v[t[i].dist].push_back(t[i].puf);
	}
	int j;
	long long int rez = 0;
	for (i=tl;i>=0;i--)
	{
		for (j=0;j<v[i].size();j++)
		{
			pq.push(v[i][j]);
			
		}
		if (!pq.empty())
		{
			rez+=pq.top();
			pq.pop();
		}
	}
	printf("%lld",rez);

	return 0;
}