Cod sursa(job #436805)

Utilizator AlexMacoMacovei Alexandru AlexMaco Data 8 aprilie 2010 23:24:12
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 1.09 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 {
			if (!taken.empty()){
				tmp = taken.top();
				if (g[i].w > tmp.w && tmp.h >){
					gathered -= tmp_w;
					gathered += g[i].w;
					taken.pop();
					taken.push(g[i]);
				}
			}
		}
	}
	printf("%d\n",gathered);
	return 0;
}