Cod sursa(job #984326)

Utilizator cont_de_testeCont Teste cont_de_teste Data 14 august 2013 09:44:55
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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


struct triple {
	int d, a, t;
	triple(): d(0), a(0), t(0) {}
	triple(const int &D, const int &A, const int &T): d(D), a(A), t(T) {}
	inline bool operator() (const triple &first, const triple &second) const {
		return first.t > second.t;
	}
};

const int MAX_N = 100100;

long long soln;
int n, x, l, up_limit;
triple a[MAX_N];

priority_queue< int, vector<int> > pq;


int main() {
	fin >> n >> x >> l;
	for (int i = 1; i <= n; ++i) {
		fin >> a[i].d >> a[i].a; // distanta; lana
		a[i].t = (x - a[i].d) / l + (a[i].d <= x);
		up_limit = max(up_limit, a[i].t);
	}
	
	sort(a + 1, a + n + 1, triple());
	
	int p = 1;
	
	for (int i = a[p].t; i >= 1; --i) {
		if (a[p].t == i) {
			int d = p;
			
			while (a[d].t == a[p].t && d <= n) {
				pq.push(a[d].a);
				++d;
			}		
			
			p = d;
		}
		if (!pq.empty()) {
			soln = soln + pq.top();
			pq.pop();
		}
	}
	
	fout << soln << '\n';
	
	fin.close();
	fout.close();
}