Cod sursa(job #344697)

Utilizator prdianaProdan Diana prdiana Data 31 august 2009 14:19:22
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <stdio.h>
#include <vector>
#include <queue>
#define MAXN 100002

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>dl)
		{
			dl = t[i].dist;
		}
	}
	v.resize(dl+1);
	for (i=0;i<nro;i++)
	{
		v[t[i].dist].push_back(t[i].puf);
	}
	int j;
	long long int rez = 0;
	for (i=dl;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;
}