Cod sursa(job #674983)

Utilizator damgoodLincan Dan damgood Data 6 februarie 2012 22:48:55
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <set>
#include <algorithm>

#define MAXN 100001

using namespace std;

int n, x, l;
int sum;

// ordonare in functie de distanta
bool comp(const pair<int,int> &left, const pair<int,int> &right)
{
	return left.first >= right.first;
}

//inserare in functie de pufosenie
struct cmp
{
	bool operator() (const int &left, const int &right)
	{
		return left >= right;
	}
};

pair<int,int> oi[MAXN]; 
set< int, cmp> h;

void read()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	
	scanf("%d %d %d ", &n, &x, &l);
	int d, c;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d %d", &d, &c);
		oi[i] = make_pair(d, c);
	}
}

void solve()
{
	sort(&oi[1], &oi[n+1], comp);
	int steps = 0;
	
	for(int i = 1; i <= n; ++i)
	{
		if( oi[i].first <= x )
		{
			h.insert( oi[i].second );
			++steps;
			x -= l;
		} else if( oi[i].second > *h.begin() )
		{
			h.erase( h.begin() );
			h.insert( oi[i].second );
		}
	}
	for(int i = 1; i <= steps; ++i)
	{
		sum += *h.begin();
		h.erase( h.begin() );
	}		
}

void printResult()
{
	printf("%d\n", sum);
}

int main()
{
	read();
	solve();
	printResult();
	return 0;
}