Cod sursa(job #503867)

Utilizator mgntMarius B mgnt Data 25 noiembrie 2010 15:33:39
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <algorithm>
using namespace std;

typedef long long int lli;
struct DA{lli d,a;};

int const maxn=100*1000;
DA A[maxn];int H[maxn];

bool cmp1(DA const &x,DA const &y){return x.d>y.d;}
bool cmp2(int x,int y){return A[x].a>A[y].a;}

int main()
{	ifstream is("lupu.in");
	ofstream os("lupu.out");
	lli N,X,L,i,m,s;is>>N>>X>>L;
	for(i=0;N>i;++i){is>>A[i].d>>A[i].a;}
	make_heap(A,A+N,cmp1);
	sort_heap(A,A+N,cmp1);
	i=0;while((i<N)&&(A[i].d>X)){++i;}
	m=0;
	while(i<N)
	{	if(A[i].d+m*L<=X)
		{H[m]=i;++m;push_heap(H,H+m,cmp2);}
		else
		{	if(A[H[0]].a<A[i].a)
			{	pop_heap(H,H+m,cmp2);
				H[m-1]=i;push_heap(H,H+m,cmp2);
			}
		}
		++i;
	}
	s=0;
	for(i=0;m>i;++i){s+=A[H[i]].a;}
	os<<s<<endl;
	return 0;
}