Cod sursa(job #436465)

Utilizator AlexMacoMacovei Alexandru AlexMaco Data 8 aprilie 2010 16:39:32
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.36 kb
#include <stdio.h>
#include <set>
#include <deque>
#include <algorithm>

using namespace std;

struct gutuie{
	int h,w;
};

/*
bool operator < (const gutuie &x, const gutuie &y){
	return x.h<
}
struct setcmp {
	bool operator() (const gutuie x, const gutuie y) const{
		return x.h<y.h;
	}
};
*/
bool sortcmp (gutuie x, gutuie y){
	return x.w>y.w;
}

/*
// intoarce cea mai mare pozitie cu h = pos
int at_end(deque<gutui> &l){

}
*/
#ifdef debug
#define P for(int i=0;i<l.size();i++){printf("(%d %d) , ", l[i].h, l[i].w);}printf("\b\b \b\b\n");
#else
#define P
#endif

void insert_in(deque<gutuie> &l, gutuie &x){
	P
#ifdef debug
	printf("(%d %d)\n",x.h, x.w);
#endif
	if (l.size() == 0){
		l.push_back(x);
		P
		return;
	}
	if (x.h < l.front().h){
		l.push_front(x);
		P
		return;
	}
	if (x.h > l.back().h){
		l.push_back(x);
		P
		return;
	}
	if (l.back().h == l.size()){
		P
		return;
	}
	if (x.h >= l.back().h){
		l.push_back(x);
		P
		return;
	}
	int a=0, b=l.size(), m;
	for(;;){
		m=(a+b)/2;
		if (x.h > m && l[m].h < x.h){
			if (l[m+1].h >= x.h){
				// insert
				l.insert(l.begin()+m+1, x);
				break;
			}
		}
		if (a==m || b==m){
			P;
			break;
		}
		if (x.h < m || l[m].h > x.h)
			b=m;
		if (l[m].h < x.h)
			a=m;
	}
	P
}

int main (){
	int n,h,u,i,j,hm=0;
	int gathered=0;
	deque<gutuie> g, taken;
	deque<gutuie>::iterator it;
	//set<gutuie,setcmp> taken;
#ifndef debug
	freopen("gutui.in","rt",stdin);
	freopen("gutui.out","wt",stdout);
#endif
	scanf("%d %d %d",&n,&h,&u);
#ifdef debug
	printf("%d %d %d\n",n,h,u);
#endif
	gutuie tmp;
	// .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",&tmp.h, &tmp.w);
#ifdef debug
		printf("(%d %d)\n",tmp.h, tmp.w);
#endif
		tmp.h=((h-tmp.h)/u)+1;
#ifdef debug
		printf("-(%d %d)\n",tmp.h, tmp.w);
#endif
		if (tmp.h>hm)
			hm=tmp.h;
		g.push_back(tmp);
	}
	
	sort(g.begin(), g.end(), sortcmp);

#ifdef debug
	for (i=0;i<g.size();i++){
		printf("(%d %d) , ", g[i].h, g[i].w);
	}
	printf("\n");
	printf("\n");
	printf("\n");
#endif


	/*
	for (i=1;i<=g.size();i++){
		if (g[i].h <= i){
			gathered += g[i].w;
			taken.insert(g[i]);
		}else{

		}
	}
	*/

	for (it = g.begin(); it != g.end(); it++){
		insert_in(taken, *it);
#ifdef debug
		printf("\n");
#endif
	}

	for (it = taken.begin(); it != taken.end(); it++)
		gathered += (*it).w;

	printf("%d\n",gathered);
	return 0;
}