Cod sursa(job #918457)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 18 martie 2013 21:36:14
Problema Lupul Urias si Rau Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

struct oita {
	int distanta,lana,strat;
};
oita oaie[100005];
int n,i,k,l;
long long totaldelana;

struct comp {
	inline bool operator()(const int &a,const int &b) {
		return (a>b);
	}
};
multiset <int,comp> heap;

bool cmp(oita a,oita b) {
	return (a.strat>b.strat);
}

int main() {
	freopen("lupu.in","r",stdin);
	freopen("lupu.out","w",stdout);
	scanf("%d %d %d",&n,&l,&k);
	for (i=1;i<=n;i++) {
		scanf("%d %d",&oaie[i].distanta,&oaie[i].lana);
		oaie[i].strat = (l-oaie[i].distanta)/k;
	}
	sort(oaie+1,oaie+n+1,cmp);
	heap.insert(oaie[1].lana);
	for (i=2;i<=n;i++) {
		if (oaie[i].strat == oaie[i-1].strat) 
			heap.insert(oaie[i].lana);
		else {
			int x = oaie[i-1].strat - oaie[i].strat;
			for (int j=1;j<=x;j++) {
				if (heap.empty()) break;
				totaldelana += (long long)*heap.begin();
				heap.erase(heap.begin());
			}
			heap.insert(oaie[i].lana);
			if (oaie[i].strat < 0) break;
		}
	}
	if (oaie[n].strat == 0 && !heap.empty()) totaldelana += (long long)*heap.begin();
	printf("%lld\n",totaldelana);
	return 0;
}