Cod sursa(job #440892)

Utilizator rurryRuxandra Nistor rurry Data 12 aprilie 2010 17:17:51
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.28 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 height < right.height;
}

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

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

  private:
    int height, weight;                              
};

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

int main()
{
	unsigned int h, u, height, weight;
	int n, i;
	Fruit x;
	Fruit2 y;
	priority_queue <Fruit> pq;
	priority_queue <Fruit2> pq2;
	
	//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, no = 1;
	unsigned int greutate = 0, ming;
	
	while (!pq.empty()) {

		height = pq.top().get_height();
		weight = pq.top().get_weight();
		if(height + no * u > h && ok > 0){
			y = Fruit2(height, weight);               
			pq2.push(y);
			ok --;
			pq.pop();
			
		}
		else
			if(!ok && height + no * u > h) {
					ming = pq2.top().get_weight();
					pq2.pop();
					if(ming > weight)
						y = Fruit2(height, ming);
					else
						y = Fruit2(height, weight); 
					pq2.push(y);
					pq.pop();
					
			}
			else{
				no ++;
				ok ++;
			}
    	//printf(">>%d %d\n\n\n\n|||", height, weight);
		}
		//printf("\n\n\n");
		while (!pq2.empty()) {
			greutate += pq2.top().get_weight();
		//	printf("%d ",pq2.top().get_height());
			pq2.pop();
		}

	fclose(fin);

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