Cod sursa(job #440917)

Utilizator angel_pacPetre Andreea Cristina angel_pac Data 12 aprilie 2010 17:42:43
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.59 kb
#include <stdio.h>
#include <fstream>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <queue>

using namespace std;

class gutui_t {
	public:
		int h;
		int g;
	public:
		gutui_t(int hval, int gval);
		gutui_t(){
			h = 0;
			g = 0;
		}
		~gutui_t(){}
		bool operator<(const gutui_t&) const;   
}; 
gutui_t::gutui_t (int hval, int gval){
	h = hval;
	g = gval;
}


bool gutui_t::operator<(const gutui_t& snd) const
{
  return g > snd.g;
}

 int comp( const void* x, const void* y){
		gutui_t fst = *(gutui_t*)x;
		gutui_t snd = *(gutui_t*)y;
		return snd.h - fst.h; 
 }
int main(){
	FILE *f=stdin,*out=stdout;
	int n, hmax, u, i, first = 1, level = 1, val = 0;
	gutui_t gutuie;
	f = fopen("gutui.in", "r");
	out= fopen("gutui.out", "w");
	//citire
	fscanf(f,"%d %d %d\n",&n, &hmax, &u);
	gutui_t *v = (gutui_t *)calloc(n, sizeof(gutui_t));
	priority_queue <gutui_t> pq;
	for (i = 0 ; i < n ;i ++){
		fscanf(f, "%d %d\n", &gutuie.h, &gutuie.g);
		if( gutuie.h <= hmax){
			//gutuie.l = (hmax - gutuie.h) / u   + 1;
			v[i] = gutuie;
		}
	}
	
 	//ordonare dupa greutate

	qsort(v, n, sizeof(gutui_t), comp);
	
	for(i = 0 ; i < n ;){
		if( ( v[i].h + level * u) > hmax && first > 0 ){
			pq.push(v[i]);
	
			first --;
			i++;
			continue;
		}
		else if( !first && (v[i].h + level * u) > hmax ){
			gutuie = pq.top();
			pq.pop();
			if(v[i].g > gutuie.g){
				pq.push(v[i]);
			}
			else{
				pq.push(gutuie);
			}
			i++;
			
		}
		else{
			level++;	
			first++;
		}
	}
	while(!pq.empty()){
		gutuie = pq.top();
		val+=gutuie.g;
		pq.pop();
	}
	
	fprintf(out, "%d", val);
	fclose(f);
	fclose(out);
	
	return 0;
}