Cod sursa(job #436787)

Utilizator AlexMacoMacovei Alexandru AlexMaco Data 8 aprilie 2010 23:12:20
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.07 kb
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

struct gutuie{
	int h,w;
};

// folosit pt priority_queue
bool operator < (const gutuie &x, const gutuie &y){
	return x.w>y.w;
}

bool sortcmp_h (gutuie x, gutuie y){
	return x.h<y.h;
}
bool sortcmp_w (gutuie x, gutuie y){
	return x.w>y.w;
}


int main (){
	int n,h,u,i;
	int gathered=0;
	gutuie g[100000];
	priority_queue<gutuie> taken;
	freopen("gutui.in","rt",stdin);
	freopen("gutui.out","wt",stdout);
	scanf("%d %d %d",&n,&h,&u);
	// .h e folosit ca numar de pasi maxim dupa care se poate culege gutuia, nu ca inaltime efectiva
	for (i=0; i<n; i++){
		scanf("%d %d",&g[i].h, &g[i].w);
		g[i].h=((h-g[i].h)/u)+1;
	}
	
	sort(g, g+n, sortcmp_w);
	stable_sort(g, g+n, sortcmp_h);

	//gutuie tmp;
	int tmp_w;
	for (i=0; i<n; i++){
		if (g[i].h >= i){
			taken.push(g[i]);
			gathered += g[i].w;
		} else {
			tmp_w = taken.top().w;
			if (!taken.empty() && g[i].w > tmp_w){
				gathered -= tmp_w;
				gathered += g[i].w;
				taken.pop();
				taken.push(g[i]);
			}
		}
	}
	printf("%d\n",gathered);
	return 0;
}