Cod sursa(job #435755)

Utilizator exquisiteDamian Alexandru exquisite Data 7 aprilie 2010 20:45:34
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.48 kb
#include <cstdio>
#include <deque>
#include <algorithm>
#include <vector>

using namespace std;

#define FIN "gutui.in"
#define FOUT "gutui.out"

bool sortPredicate(const pair<int, int> &a, const pair<int, int> &b) {
	return (a.first == b.first) ? (a.second > b.second) : (a.first < b.first);
}

bool greaterEq(const int &a, const int &b) {
	return a >= b;
}


void moveDequeHeap(deque<int>& Q, vector<int>& V) {
	while(Q.size()) {
		V.push_back(Q.back());
		push_heap(V.begin(), V.end(), greaterEq);
		Q.pop_back();
	}
	return;
}

int main() {
	FILE *fin = fopen(FIN, "rt");
	FILE *fout = fopen(FOUT, "wt");
	int n, h, u;

	fscanf(fin, "%d %d %d", &n, &h, &u);
	
	vector< pair <int, int> > A;	
	int x, y;

	for (int i = 0; i < n; i++) {
		fscanf(fin, "%d %d", &x, &y);
		if (h >= x) A.push_back(pair<int, int>(1 + (h - x) / u, y));
	}

	sort(A.begin(), A.end(), sortPredicate);

	deque<int> Q;
	vector<int> V;
	int interval = (A.size()) ? (A[0].first) : 0;
	for (vector< pair<int, int> >::iterator i = A.begin(); i < A.end();) {
		if (i->first > interval) {
			interval++;
			moveDequeHeap(Q, V);
			continue;
		}
		if (Q.size() < interval - V.size()) Q.push_back(i->second);
		else if (V.size() != 0 && V.front() < i->second) {
			pop_heap(V.begin(), V.end(), greaterEq);
			V.pop_back();
			Q.push_back(i->second);
		}
		i++;
	}
	moveDequeHeap(Q, V);
	int sum = 0;
	for (vector<int>::iterator i = V.begin(); i < V.end(); i++) sum += (*i);
	fprintf(fout, "%d\n", sum);
	
	fclose(fin);
	fclose(fout);
	return 0;
}