Cod sursa(job #424584)

Utilizator galacticaBattlestar galactica Data 24 martie 2010 22:41:22
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 0.85 kb
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int N,H,U;
priority_queue <int,vector<int>,greater<int> > Q;

struct gutuie{
	int fs,sc;
}nr[100100];
struct cmp{
	bool operator()(const gutuie &a,const gutuie &b)const{
		if(a.fs==b.fs)
			return a.sc>b.sc;
		return a.fs<b.fs;
	}
};

int main(){
	freopen("gutui.in","r",stdin);
	freopen("gutui.out","w",stdout);
	int i,x,y,h=0;
	scanf("%d%d%d",&N,&H,&U);
	for(i=0;i<N;++i){
		scanf("%d%d",&x,&y);
		nr[i].fs=(H-x)/U+1;
		nr[i].sc=y;
	}
	sort(nr,nr+N,cmp());
	for(i=0;i<N;++i){
		if(h+1<=nr[i].fs){
			Q.push(nr[i].sc);
			++h;
		}
		else{
			if(Q.top()<nr[i].sc){
				Q.pop();
				Q.push(nr[i].sc);
			}
		}
	}
	x=0;
	while(!Q.empty()){
		x+=Q.top();
		Q.pop();
	}
	printf("%d\n",x);
	fclose(stdin);
	fclose(stdout);
	return 0;
}