Cod sursa(job #197228)

Utilizator alexeiIacob Radu alexei Data 2 iulie 2008 21:52:38
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <set>
#include <algorithm>
#define nmax 100024

using namespace std;
class set_cmp{
public:
    bool operator()(const long long  &a,const long long  &b)
    { 
         return (a > b); 
    };
};
/*
inline int cmp(const long long a,const long long b)
{
       if( a>b )
       return a;
       return b;
}*/

typedef struct{
        long long timp,cost;
        }q;
q v[nmax];

inline int cmp(q A,q B){  
     return A.timp<B.timp;  
}  

multiset <long long, set_cmp> w; //STL trick

int main()
{

	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	
	long long N,X,L;
	
	scanf("%lld%lld%lld\n",&N,&X,&L);
	
	long long n=0;
    long long i;
	long long a1,a2;
    long long solfin=0;
    
    for (i=1; i<=N; ++i)
	{
		scanf("%lld%lld", &a1, &a2);
		
        if( a1<=X ) 
		{
        ++n;
        v[n].timp = (X-a1)/L;
	    v[n].cost = a2;
	    }
        
    }
	N=n;
    sort(v+1, v+N+1,cmp);
	
    for(i=v[N].timp; i>=0; --i)
	{
		while( v[n].timp==i && n>0 )
		{
			w.insert(v[n].cost);
			--n;
		}
		if (!w.empty())
		{
			solfin+=*w.begin();
			w.erase(w.begin());
		}
	}
	printf("%lld\n", solfin);
	return 0;
}