Cod sursa(job #490394)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 6 octombrie 2010 15:04:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <fstream>
#include <algorithm>
using namespace std;
#define DIM 100001

struct oaie {
	int L, T;
};

oaie A[DIM];
int N, X, L, NH, H[DIM];
long long R;

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

void swap (int &a, int &b) {
	int x=a; a=b; b=x;
}

int cmp (oaie a, oaie b) {
	return a.T > b.T;
}

void cit () {
	fin >> N >> X >> L;
	for (int i=1, d, x; i<=N; ++i) {
		fin >> d >> x;
		A[i].L = x;
		A[i].T = (X - d) / L + 1;
	}
}

void heap_add (int poz) {
	while (poz/2 >= 1 && H[poz] > H[poz/2]) {
		swap (H[poz], H[poz/2]);
		poz /= 2;
	}
}

void heap_rmv (int poz) {
	while (poz*2 <= NH) {
		poz *= 2;
		if (poz+1 <= NH && H[poz] < H[poz+1])
			poz++;
		if (H[poz] > H[poz/2])
			swap (H[poz], H[poz/2]);
	}
}

void parc () {
	for (int t=A[1].T, oc=1; t >= 1; --t) {
		while (A[oc].T == t) {
			H[++NH] = A[oc++].L;
			heap_add (NH);
		}
		if (NH > 0) {
			R += (long long) H[1];
			H[1] = H[NH--];
			heap_rmv (1);
		}		
	}
}

void afs () {
	fout << R;
}

int main () {
	
	cit ();
	sort (A+1, A+1+N, cmp);
	parc ();
	afs ();
	
	return 0;	
}