Cod sursa(job #419656)

Utilizator svalentinValentin Stanciu svalentin Data 17 martie 2010 19:37:30
Problema Gutui Scor Ascuns
Compilator cpp Status done
Runda Marime 1.21 kb
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

int n, h, u, t=0;
vector<pair<int, int> > elem;
vector<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.push_back(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()) {
					nth_element(ss.begin(), ss.end()-1, ss.end()); // make the last element the biggest
					t += *(ss.end()-1);		// get it
					ss.erase(ss.end()-1);	// erase it
				}
			}
		}
		ss.push_back(elem[i].second);
//		printf("h=%d, t=%d\n", height, t);
	}
	for ( ; height>0; --height) {
		if (!ss.empty()) {
			nth_element(ss.begin(), ss.end()-1, ss.end()); // make the last element the biggest
			t += *(ss.end()-1);
			ss.erase(ss.end()-1);
		}
	}
	
	printf("%d\n", t);
	
	return 0;
}