Cod sursa(job #821355)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 22 noiembrie 2012 10:59:58
Problema Lupul Urias si Rau Scor 88
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

#define f first
#define s second

vector<pair<int, int> > V;
priority_queue<int> PQ;
int N, X, L, T;
long long rez;

void read_data() {
	
	freopen("lupu.in","r",stdin);
	int i, dist, cant, timp;
	
	scanf("%d %d %d",&N, &X, &L);
	V.resize(N+1);
	for(i=1; i<=N; ++i) {
		scanf("%d %d",&dist, &cant);
		// calculez timpul cand o oaie poate fi mancata de lup
		if(L) 
			timp = (X-dist) / L + 1;
		else
			timp = X - dist + 1;
		V[i].f = timp;
		V[i].s = cant;
	}
	sort(V.begin()+1, V.end());
}

void solve() {
	
	int i, j;
	
	T = V[N].f;
	j = N;
	for(i=T; i>=1 && j>=1; --i) {
		while(V[j].f == i && j>=1) {
			PQ.push(V[j].s);
			--j;
		}
		rez += 1LL*PQ.top();
		PQ.pop();
	}
}

void print_rez() {
	
	freopen("lupu.out","w",stdout);
	printf("%lld\n",rez);
}

int main() {
	
	read_data();
	solve();
	print_rez();
	
	return 0;
}