Cod sursa(job #143709)

Utilizator tvladTataranu Vlad tvlad Data 26 februarie 2008 20:02:58
Problema Lupul Urias si Rau Scor 44
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

struct oaie { int w,d; };

const int N = 10;//100000;

int n;
oaie o[N];

bool sort_cmp ( const oaie &a, const oaie &b ) { return (a.d > b.d); };
class set_cmp {
public:
	bool operator() ( const oaie &a, const oaie &b ) { return (a.w > b.w); };
};

int main() {
	freopen("lupu.in","rt",stdin);
	freopen("lupu.out","wt",stdout);
	int x, dp;
	scanf("%d %d %d",&n,&x,&dp);
	for (int i = 0; i < n; ++i) {
		scanf("%d %d",&o[i].d,&o[i].w);
		o[i].d = ((x-o[i].d)/dp)+1;
	}
	sort(o,o+n,sort_cmp);
	int r = 0;
	multiset<oaie,set_cmp> heap;
	for (int t = o[0].d, i = 0; t; --t) {
		for (; o[i].d == t; heap.insert(o[i]), ++i);
		if (!heap.empty()) {
			r += heap.begin()->w;
			heap.erase(heap.begin());
		}
	}
	printf("%d\n",r);
	return 0;
}