Cod sursa(job #143758)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 26 februarie 2008 20:35:12
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int N_MAX = 100010;
const int INF = 2000000000;

bool fncomp (pair<int, int> lhs, pair<int, int> rhs) {return lhs.second > rhs.second;}

struct classcomp {
	  bool operator() (const pair<int, int>& lhs, const pair<int,int>& rhs) const
		    {return lhs.second > rhs.second;}
};

int size = 0;
multiset <pair <int, int>, classcomp > H;
pair <int, int> vec[N_MAX];

int cmp(pair <int, int> a, pair <int, int> b)
{
	return (a.first > b.first);
}

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

	int N, X, L, i, y, l;

	scanf("%d %d %d\n", &N, &X, &L);
	for (i = 1; i <= N; i ++) {
		scanf("%d %d\n", &y, &l);
		vec[i] = make_pair((X - y) / L, l);
	}
	sort(vec + 1, vec + N + 1, cmp);
	
	int tmax = vec[1].first, poz = 1;
	long long rez = 0;

	for (i = tmax; i >= 0; i --) {
		while (vec[poz].first == i && poz <= N) {
			H.insert(make_pair(i, vec[poz].second));
			poz ++;
		}
		
		rez += H.begin() -> second;
		H.erase(H.begin());
	}
	
	printf("%lld\n", rez);
	
	return 0;
}