Cod sursa(job #437961)

Utilizator rurryRuxandra Nistor rurry Data 10 aprilie 2010 12:33:20
Problema Gutui Scor 60
Compilator cpp Status done
Runda teme_upb Marime 1.59 kb
//NISTOR RUXANDRA
//321 CA

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>

using namespace std;

class Fruit
{
  public:
    Fruit() {};                                    
    Fruit(int x, int y) { height = x; weight = y; }    
    bool operator<(const Fruit&) const;             

    int get_height() const { return height; }       
    int get_weight() const { return weight; }

  private:
    int height, weight;                              
};

bool Fruit::operator<(const Fruit& right) const
{
  return weight < right.weight;
}

int main()
{
	unsigned int h, u, height, weight, ref_height;
	int n, i;
	Fruit x;
	priority_queue <Fruit> pq;
	
	//se citesc datele din fisier
	FILE *fin = fopen("gutui.in", "r");
	fscanf(fin, "%d", &n);
	fscanf(fin,"%u", &h);
	fscanf(fin, "%u", &u);

	for(i = 0; i < n; i++){
		fscanf(fin, "%u %u", &height, &weight);
		x = Fruit(height, weight);               
		pq.push(x);
	}

	int ok = 1;
	unsigned int greutate = 0;
	while (ok){
		ok = 0;
		if(!pq.empty()){
			greutate += pq.top().get_weight();
			ref_height = pq.top().get_height();
			pq.pop();
			ok = 1;
		}
		priority_queue <Fruit> pq2;
		while (!pq.empty()) {
			weight = pq.top().get_weight();
			height = pq.top().get_height();
			pq.pop();
			// daca se afla pe un nivel mai jos
			if((h - height)/ u + 1 >= (h - ref_height)/u +1)
				height +=u;		
			if(height <= h){
				x = Fruit(height, weight); 
				pq2.push(x);
			}
		}
		pq = pq2;
	}
			
	
	fclose(fin);

	FILE *fout = fopen("gutui.out", "w");
	fprintf(fout, "%u", greutate);
	fclose(fout);
	//printf(">>>>>%d", greutate);	
	
	return 0;
}