Cod sursa(job #434842)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 6 aprilie 2010 17:13:50
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.63 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){
			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 ){
				 if(lev == 0 && ((gutuie.h + gutuie.l * u) == hmax)){
						ocupat[0] = 1;
						val+=gutuie.g;
				 }
				 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;
}