Cod sursa(job #464104)

Utilizator bora_marianBora marian bora_marian Data 18 iunie 2010 20:11:31
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<fstream>
#include<algorithm>
#include<queue>
using namespace std;
int n,x,l;
struct nod{
   int dist;
   int lana;
   int timp;};
nod v[1000002];
long long maxim,val,sol;
priority_queue<long long> h;
int  cmp(nod a,nod b);
int main()
{
	ifstream fin("lupu.in");
	ofstream fout("lupu.out");
	fin>>n>>x>>l;
	int i,j;
	for(i=1;i<=n;i++)
		fin>>v[i].dist>>v[i].lana;
	int pp=0;
	for(i=1;i<=n;i++)
	{	
		v[i].timp=(x-v[i].dist)/l;
		if(v[i].dist<x)
			v[i].timp++;
		if(v[i].timp>maxim)
			maxim=v[i].timp;
	}
	val=n;
	sort(v+1,v+n+1,cmp);
	//for(i=1;i<=n;i++)
		//fout<<v[i].lana<<" "<<v[i].timp<<endl;
	for(j=maxim;j>=1;j--)
	{
		int pp=0;
		for(i=val;pp==0;i--)
			if(v[i].timp!=j)
				val=i,pp=1;
			else
				h.push(v[i].lana);
		if(h.size())
		{
			sol+=h.top();
			//fout<<h.top()<<endl;
			h.pop();
		}
	}
    fout<<sol;
	return 0;
}
int  cmp(nod a,nod b)
{
	
	if(a.timp>b.timp)
		return 0;
	return 1;
}