Cod sursa(job #998587)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 17 septembrie 2013 18:20:56
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int n,X,L,Tmax;
struct Oaie{
	int d,lana,t;
	bool operator <(const Oaie &A) const
	{
		return t>A.t;
	}
};
Oaie v[100100];
long long sol;
vector <int> H;

int main()
{
	int i,j;
	ifstream fin("lupu.in");
	fin>>n>>X>>L;
	for(i=1;i<=n;i++)
	{
		fin>>v[i].d>>v[i].lana;
		v[i].t=(X-v[i].d)/L+1;
		Tmax=max(Tmax,v[i].t);
	}
	fin.close();
	
	sort(v+1,v+n+1);
	for(i=Tmax,j=1;i>0;i--)
	{
		while(j<=n && v[j].t==i)
		{
			H.push_back(v[j].lana);
			push_heap(H.begin(),H.end());
			j++;
		}
		if(H.size())
		{
			sol+=1LL*H[0];
			pop_heap(H.begin(),H.end());
			H.pop_back();
		}
	}
	
	ofstream fout("lupu.out");
	fout<<sol<<"\n";
	fout.close();
	return 0;
}