Cod sursa(job #419686)

Utilizator svalentinValentin Stanciu svalentin Data 17 martie 2010 20:25:10
Problema Gutui Scor Ascuns
Compilator cpp Status done
Runda Marime 1.22 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) {
				int bigp = -1;
				for (int i=0; i<ss.size(); ++i)
					if (bigp==-1 || ss[i] > ss[bigp])
						bigp = i;
				if (bigp != -1) {
					t += ss[bigp];
					ss.erase(ss.begin()+bigp);
				}
			}
		}
		ss.push_back(elem[i].second);
//		printf("h=%d, t=%d\n", height, t);
	}
	for ( ; height>0; --height) {
		int bigp = -1;
		for (int i=0; i<ss.size(); ++i)
			if (bigp==-1 || ss[i] > ss[bigp])
				bigp = i;
		if (bigp != -1) {
			t += ss[bigp];
			ss.erase(ss.begin()+bigp);
		}
	}
	
	printf("%d\n", t);
	
	return 0;
}