Cod sursa(job #821357)

Utilizator brainwashed20Alexandru Gherghe brainwashed20 Data 22 noiembrie 2012 11:01:43
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 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
		timp = (X-dist) / L + 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 && j>=1; --i) {
		while(V[j].f == i && j>=1) {
			PQ.push(V[j].s);
			--j;
		}
		if(!PQ.empty()) {
			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;
}