Cod sursa(job #1320151)

Utilizator vld7Campeanu Vlad vld7 Data 17 ianuarie 2015 17:30:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

#define x first
#define y second
#define PII pair <int, int>

ifstream in ("lupu.in");
ofstream out ("lupu.out");

bool cmp (PII X, PII Y) {
	return X.x > Y.x;
}

int N, X, L;
long long ans;

vector <PII> V;
priority_queue <int> heap;

int main() {
	in >> N >> X >> L;
	
	for (int i = 0; i < N; i++) {
		// D + t * L > X <=> t > (X - D) / L
		int D, A, t;
		
		in >> D >> A;
		if (X < D)
			t = 0;
		else
			t = (X - D) / L + 1;
		
		V.push_back (make_pair (t, A));
	}
	
	sort (V.begin(), V.end(), cmp);
	
	int index = 0;
	for (int i = N; i >= 1; i--) {
		while (V[index].x >= i) {
			heap.push (V[index].y);
			index++;
		}
		if (!heap.empty()) {
			ans += 1LL * heap.top();
			heap.pop();
		}
	}
	
	out << ans;
	
	return 0;
}