Cod sursa(job #439779)

Utilizator victor_u_roVictor Ungureanu victor_u_ro Data 11 aprilie 2010 19:16:07
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.46 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100024

struct gutuie {
	long t, g;

	bool compg(gutuie x) const {
		if (g < x.g)
			return true;
		
		return false;
	}
	
	bool operator<(gutuie x) const {
		return compg(x);
	}
};

long n, gmax;
gutuie a[NMAX];

void cit() {
	long h, u;
	long i, nn;

	freopen("gutui.in", "rt", stdin);
	
	scanf("%ld %ld %ld", &n, &h, &u);
	nn = 0;
	for (i = 0; i < n; i++) {
		scanf("%ld %ld", &a[nn].t, &a[nn].g);
		
		if (a[nn].t <= h) {
			a[nn].t = (h - a[nn].t) / u;
			nn++;
		}
		
	}
	n = nn;
	
	fclose(stdin);
}

bool compt(gutuie x, gutuie y) {	
	if (x.t == y.t) {
		if (x.g > y.g)
			return true;

		return false;
	}
	
	if (x.t < y.t)
		return true;
	
	return false;
}

void rez() {
	long lt, ng, i, hsize;
	gutuie b[NMAX];

	sort(a, a + n, compt);
	
	/*for (i = 0; i < n; i++)
		printf("%ld/%ld ", a[i].t, a[i].g);
	printf("\n");*/
	
	ng = 0;
	lt = a[0].t;
	gmax = a[0].g;
	hsize = 0;
	for (i = 1; i < n; i++) {
		if (lt != a[i].t) {
			ng += a[i].t - lt;
			if (i == n - 1)
				ng += a[i].t;
			lt = a[i].t;
		}
		
		b[hsize++] = a[i];
		push_heap(b, b + hsize);
	
		for (; ng > 0 && hsize > 0; ng--, hsize--) {
			pop_heap(b, b + hsize);
			gmax += b[hsize - 1].g;
		}
		
		/*for (int j = 0; j < hsize; j++)
			printf("%ld/%ld ", b[j].g, b[j].t);
		printf("\n");*/
	}
}

void afis() {
	freopen("gutui.out", "wt", stdout);
	
	printf("%ld\n", gmax);
	
	fclose(stdout);
}

int main() {
	cit();
	rez();
	afis();

	return 0;
}