Cod sursa(job #490376)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 6 octombrie 2010 11:16:59
Problema Lupul Urias si Rau Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIM 100001

struct oaie {
	int D, L, T;
};

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

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

void cit () {
	scanf ("%d%d%d", &N, &X, &L);
	for (int i=1; i<=N; ++i) {
		scanf ("%d%d", &A[i].D, &A[i].L);
		A[i].T = (X - A[i].D) / L + 1; 
	}
}

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

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

void parc () {
	for (int i=1, t=A[1].T; i <= N && t >= 1; --t) {
		while (i <= N && A[i].T == t) {
			H[++NH] = A[i++].L;
			heap_u ();
		}
		if (NH >= 1) {
			Lana += H[1];
			H[1] = H[NH--];
			heap_d ();
		}		
	}
}

void afs () {
	printf ("%lld", Lana);
}

int main () {
	freopen ("lupu.in", "r", stdin);
	freopen ("lupu.out", "w", stdout);
	
	cit ();
	sort (A+1, A+N+1, cmp);
	parc ();
	afs ();
	
	return 0;
}