Cod sursa(job #435739)

Utilizator exquisiteDamian Alexandru exquisite Data 7 aprilie 2010 20:23:15
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.02 kb
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <vector>

using namespace std;

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

bool sortPredicate(const pair<unsigned long, unsigned long> &a, const pair<unsigned long, unsigned long> &b) {
	if (a.first == b.first) return a.second > b.second;
	else return a.first < b.first;
}

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


void moveDequeHeap(deque<unsigned long>& Q, vector<unsigned long>& 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");
	unsigned long n, h, u;

	fscanf(fin, "%lu %lu %lu", &n, &h, &u);
	
	vector< pair <unsigned long, unsigned long> > A;	
	unsigned long x, y;

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

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

	deque<unsigned long> Q;
	vector<unsigned long> V;
	unsigned long interval = (A.size()) ? (A[0].first) : 0;
	for (vector< pair<unsigned long, unsigned long> >::iterator i = A.begin(); i < A.end();) {
		//printf("~%lu %lu %lu~\n", i->first, i->second, interval);
		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);
		}
		//for (vector<unsigned long>::iterator it = V.begin(); it < V.end(); it++) printf("%lu ", *it);
		//printf("    :V\n");
		//for (deque<unsigned long>::iterator it = Q.begin(); it < Q.end(); it++) printf("%lu ", *it);
		//printf("    :Q\n");
		i++;
	}
	moveDequeHeap(Q, V);
	unsigned long sum = 0;
	for (vector<unsigned long>::iterator i = V.begin(); i < V.end(); i++) sum += (*i);
	fprintf(fout, "%lu\n", sum);
	
	fclose(fin);
	fclose(fout);
	return 0;
}