Cod sursa(job #441098)

Utilizator daniel.tabacaruTabacaru Daniel daniel.tabacaru Data 12 aprilie 2010 19:19:21
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 2.41 kb
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <queue>

using namespace std;

typedef struct gutui {
        int height;
        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
{
  //bool reverse;
public:
  //mycomparison(const bool& revparam=false)
    //{reverse=revparam;}
  bool operator() (const int& lhs, const int&rhs) const
  {
       return (lhs>rhs);
  }
}; 

int main() 
{
    int N, H, U;
    int i, greutate = 0;
    FILE *f, *g;
    Gutui v[100];
    
priority_queue< int, vector<int>, mycomparison > culese;
    //multimap <int,int>::iterator it;
    
    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", &v[i].height, &v[i].weight);
    }  
        
    for (i=0; i<N; i++)
    {
         v[i].pasi = (H - v[i].height)/U + 1; 
    }
    
    qsort(v, N, sizeof(Gutui), compare);
    
    /*for (i=0; i<N; i++)
    {
         printf("%d %d\n",v[i].pasi,v[i].weight);
    }
    printf("\n");*/
    
    
   greutate = 0;
    int k=0;
    //int nr = v[0].pasi;
    
    
    
    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)
        {
             printf("s=%d t=%d\n",culese.size(),culese.top());
           if (v[i].weight > culese.top())
              {
                 greutate -= culese.top();
                 culese.pop();

                 greutate += v[i].weight;
                 culese.push(v[i].weight);
              }
           }    
    }  
   /*while (!culese.empty())
  {
     cout << "  " << culese.top();
     culese.pop();
  }
        
        
        printf("\nGreutatea este %d", greutate);*/
    
    getchar();
    fprintf(g,"%d",greutate);
    fclose(f);
    fclose(g);
    return 0;
}