Cod sursa(job #436833)

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