Cod sursa(job #421203)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 21 martie 2010 12:20:27
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.13 kb
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

int n, h, u, t=0;
vector<pair<int, int> > elem;
multiset<int> ss;

int main(void)
{
	freopen("gutui.in", "rt", stdin);
	freopen("gutui.out", "wt", stdout);
	
	scanf("%d%d%d", &n, &h, &u);
	for (int i=0, x, y; i<n; ++i) {
		scanf("%d%d", &y, &x);
		y = (h-y) / u + 1;
		if (y>0)
			elem.push_back(make_pair(y, x));
	}
	
	sort(elem.rbegin(), elem.rend());	// sort desc
	
//	for (int i=0; i<n; ++i)
//		printf("%d %d\n", elem[i].first, elem[i].second);
	
	n = elem.size();
	ss.insert(elem[0].second);	
	int height=elem[0].first;
	
	for (int i=1; i<n; ++i) {
		if (elem[i].first < elem[i-1].first) {
			for ( ; height>elem[i].first; --height) {
				if (!ss.empty()) {
					t += *ss.rbegin();		// get largest element
					ss.erase(--ss.end());	// erase it
				}
			}
		}
		ss.insert(elem[i].second);
//		printf("h=%d, t=%d\n", height, t);
	}
	for ( ; height>0; --height) {
		if (!ss.empty()) {
			t += *ss.rbegin();		// get largest element
			ss.erase(--ss.end());	// erase it
		}
	}
	
	printf("%d\n", t);
	
	return 0;
}