Cod sursa(job #712009)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 12 martie 2012 22:32:35
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>
#define NMAx 100100
#define timp first
#define profit second
#define left(i) (2*i)
#define right(i) (2*i+1)
#define father(i) (i/2)
#define cmp(a,b) (V[Heap[a]].profit>V[Heap[b]].profit)
using namespace std;

pair <int,int> V[NMAx];
int N,X,L,Vf,Heap[NMAx];
long long Sol;

void Up(int nod) {
	
	while(nod>1&&cmp(nod,father(nod))) {
		swap(Heap[nod],Heap[father(nod)]);
		nod=father(nod);
		}
	
}
void Down(int nod) {
	
	int son;
	do {
		son=0;
		if(left(nod)<=Vf) {
			son=left(nod);
			if(right(nod)<=Vf&&cmp(right(nod),left(nod)))
				son=right(nod);
			if(cmp(nod,son))
				son=0;
			}
		
		if(son) {
			swap(Heap[nod],Heap[son]);
			nod=son;
			}
		
	}while(son);
	
}
void citire() {
	
	ifstream in("lupu.in");
	in>>N>>X>>L;
	
	for(int i=1;i<=N;i++) {
		in>>V[i].timp>>V[i].profit;
		V[i].timp=(X-V[i].timp)/L+1;
		}
	
	in.close();
	
}
int main() {
	
	int i,k;
	citire();
	
	sort(V+1,V+N+1);
	reverse(V+1,V+N+1);
	
	for(k=V[1].timp,i=1;k>=1;k--) {
		
		for(;V[i].timp>=k&&i<=N;i++) {
			Heap[++Vf]=i;
			Up(Vf);
			}
		
		Sol+=V[Heap[1]].profit;
		Heap[1]=Heap[Vf--];
		Down(1);
		}
	
	ofstream out("lupu.out");
	out<<Sol<<'\n';
	out.close();
	
	return 0;
	
}