Cod sursa(job #438886)

Utilizator victor_u_roVictor Ungureanu victor_u_ro Data 11 aprilie 2010 02:22:47
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.07 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define NMAX 100000

struct gutuie {
	long t, g;

	bool comp(gutuie x) const {	
		if (t == x.t) {
			if (g >= x.g)
				return true;

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

long n, gmax;
gutuie a[NMAX];

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

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

void rez() {
	long lt, ng, i;

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

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

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

	return 0;
}