Cod sursa(job #435307)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 7 aprilie 2010 11:48:32
Problema Gutui Scor 20
Compilator cpp Status done
Runda teme_upb Marime 1.65 kb
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <list>

using namespace std;

class gutui_t {
	public:
		int h;
		int g;
		int  l;
	public:
		gutui_t(int hval, int gval, int lval);
		gutui_t(){
			h = 0;
			g = 0;
			l = 0;
		}
		~gutui_t(){}
}; 
gutui_t::gutui_t (int hval, int gval, int lval){
	h = hval;
	g = gval;
	l = lval;
}


fstream f("gutui.in",ios::in);
fstream out("gutui.out",ios::out);

bool compare (gutui_t fst, gutui_t snd)
{
	if ( fst.g > snd.g)
		return true;
	if(fst.g == snd.g && fst.l <= snd.l)
		return true;
	return false;
}


int main(){
	int n, hmax, u, i;
	list <gutui_t> v;
	gutui_t gutuie;
	int h, g, val = 0;   

	f>>n;
	f>>hmax;
	f>>u;
	for (i = 0; i< n; i++){
		f>>h>>g;
		gutuie.h = h;
		gutuie.g = g;
		if( h <= hmax){
			if( h == hmax)
				gutuie.l = 0;
				else{	
					if(gutuie.h%u)
							gutuie.l = (hmax/u) - gutuie.h/u-1;
					else
							gutuie.l = (hmax/u) - gutuie.h/u;
					}
			v.push_back(gutuie);
		}
	}
	int lev = 0;
	v.sort(compare);
	int *ocupat = (int *)calloc(hmax/u, sizeof(int));
	//culeg
	//list<gutui_t>::iterator it;
	//for(it=v.begin(); it != v.end(); ++it) cout << (*it).h <<" "<<(*it).g<<" "<<(*it).l<<endl;
	while(!v.empty()){
		
		
		gutuie = v.front();
		v.pop_front();
		if( !ocupat[gutuie.l]){
				val += gutuie.g;
				ocupat[gutuie.l] = 1;
		}
		else {
			 lev = gutuie.l;
			 while(lev >= 0 && ocupat[lev]==1 )
					lev--;
			 if(lev >= 0 ){
					ocupat[lev] = 1;
					val+=gutuie.g;
				
			 }
		}
		//printf("greutate = %d\n", gutuie.g);
		//printf("val = %d\n", val);
		//for(i = 0; i< hmax/u; i++)
			//printf("%d ", ocupat[i]);
		//printf("\n");
	}
	

	out<<val;
	return 0;
}