Cod sursa(job #1264507)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 15 noiembrie 2014 21:37:30
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 0.66 kb
#include<cstdio>
#include<algorithm>
#include<queue>

using namespace std;
const int NMAX = 100005;

int N,X,L,i,D,A,M,t;
long long sol,add;
struct Sheep {int d,a;} P[NMAX];
priority_queue<int> PQ;

bool cmp(Sheep A,Sheep B)
{
    return A.d<B.d;
}

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

	scanf("%d%d%d",&N,&X,&L);
	for(i=1;i<=N;i++)
	{
	    scanf("%d%d",&D,&A);
	    if(D<=X) P[++M].d=(X-D)/L+1, P[M].a=A;
	}

	N=M; sort(P+1,P+N+1,cmp);
	for(i=N,t=P[N].d;t;t--)
	{
	    while(i && P[i].d==t) PQ.push(P[i].a), i--;
        if(!PQ.empty()) sol+=PQ.top(), PQ.pop();
	}
	printf("%lld\n",sol);

	return 0;
}