Cod sursa(job #441495)

Utilizator daniel.tabacaruTabacaru Daniel daniel.tabacaru Data 12 aprilie 2010 22:38:37
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.07 kb
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>

using namespace std;

typedef struct gutui {
        int weight;
        int pasi;
} Gutui;


int compare(const void *a, const void *b) {
	Gutui* ob1 = (Gutui*) a;
	Gutui* ob2 = (Gutui*) b;
	if (ob1->pasi != ob2->pasi) {
               if (ob1->pasi < ob2->pasi) return -1;
                  else return 1;
               }
    if (ob1->pasi == ob2->pasi) {
               if (ob1->weight < ob2->weight) return 1;
                  else return -1;
               }         
	return 0;
}     

class mycomparison
{
public:
  bool operator() (const int& lhs, const int &rhs) const
  {
       return (lhs>rhs);
  }
}; 

int main() 
{
    int N, H, U;
    int i, j, greutate = 0;//j reprezinta inaltimea gutuii
    FILE *f, *g;
    Gutui v[100000];
    
    priority_queue< int, vector<int>, mycomparison > culese;

    
    f = fopen("gutui.in", "r");
    g = fopen("gutui.out", "w");
    
    fscanf(f, "%d %d %d", &N, &H, &U);
    
    for (i=0; i<N; i++)
    {
        fscanf(f, "\n%d %d", &j, &v[i].weight);
        v[i].pasi = (H - j)/U + 1;  //construim vectorul de pasi; adica dupa cate ridicari ale copacului, nu mai putem culege gutuia curenta
    }  
        
    
    qsort(v, N, sizeof(Gutui), compare);//sortam crescator dupa nr de pasi, si in caz de egalitate descrescator dupa greutatea gutuii
    
    int k=0; //reprezinta cate gutui s-au cules

    
    for (i=0; i<N; i++)
    {
        if (v[i].pasi - k > 0)
           {
               culese.push(v[i].weight);
               k++;  
               greutate += v[i].weight;  
           }
        else if(culese.size()>0)
        {
           if (v[i].weight > culese.top())
              {
                 greutate -= culese.top();
                 culese.pop();
                 greutate += v[i].weight;
                 culese.push(v[i].weight);
              }
           }    
    }  
   
    fprintf(g,"%d",greutate);
    
    fclose(f);
    fclose(g);
    
    return 0;
}