Cod sursa(job #439476)

Utilizator daniel.pleteaPletea Daniel daniel.pletea Data 11 aprilie 2010 16:29:40
Problema Lupul Urias si Rau Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.81 kb
#include <stdio.h>
//#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <iterator>
#include <functional>
#include <numeric>

/* PRINT_ELEMENTS()
 * - prints optional C-string optcstr followed by
 * - all elements of the collection coll
 * - separated by spaces
 */
template <class T>
inline void PRINT_ELEMENTS (const T& coll, const char* optcstr="")
{
    typename T::const_iterator pos;

    std::cout << optcstr;
    for (pos=coll.begin(); pos!=coll.end(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
}

/* INSERT_ELEMENTS (collection, first, last)
 * - fill values from first to last into the collection
 * - NOTE: NO half-open range
 */
template <class T>
inline void INSERT_ELEMENTS (T& coll, int first, int last)
{
    for (int i=first; i<=last; ++i) {
        coll.insert(coll.end(),i);
    }
}

using namespace std;

FILE* fs;
FILE* fd;
int N, max_height, height_inc,i,j,x,max_weight=0,increase=0,rest, cate_gutui, max, k, maxh;//,min,k, minmin,//kk,kkk,kkkk,maxh,r; 
int aux;

/*void insert(int value, nod arb)
{
     if(arb.value<value) 
     {
        aux = arb.value;
        arb.value=value;
        insert_end(
     }
}*/

typedef struct {
   int height;
   int weight;
} gutuie;

gutuie tree[100001];

int compare (const void * a, const void * b)
{
  if(  ( (*(gutuie*)a).height - (*(gutuie*)b).height )  == 0 )
    return ( (*(gutuie*)b).weight - (*(gutuie*)a).weight );
  else return ( (*(gutuie*)a).height - (*(gutuie*)b).height ); 
}


main() {
    int i, j;

    
    
    vector<int> coll;

    //INSERT_ELEMENTS(coll,3,7);
    //INSERT_ELEMENTS(coll,5,9);
    //INSERT_ELEMENTS(coll,1,4);

    //PRINT_ELEMENTS (coll, "on entry:           ");

    // convert collection into a heap
    make_heap (coll.begin(), coll.end());
    //coll.push_back (17);
    //push_heap (coll.begin(), coll.end());
    
    //x = coll.front();
    //printf("salu %i \n", x);
    //pop_heap(coll.begin(), coll.end());
    //coll.pop_back();
    
    
    //PRINT_ELEMENTS (coll, "after make_heap():  ");
    
    fs = fopen("lupu.in","r");
    fd = fopen("lupu.out","w");
    
    if (fs==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    if (fd==NULL) {
       printf("Eroare");
       exit (1);
    }
    
    
    
    maxh=0;
    fscanf(fs,"%i",&N);   
    fscanf(fs,"%i",&max_height);
    fscanf(fs,"%i",&height_inc);
    rest = max_height%height_inc;
    max_height=max_height/height_inc;
    //printf("salut");
    for(i=0;i<N;i++){
       fscanf(fs,"%i",&x);
       if(x%height_inc>rest)
          tree[i].height = x / height_inc + 1;
       else
          tree[i].height = x / height_inc;
       fscanf(fs,"%i",&x);
       tree[i].weight = x;
       if(maxh<tree[i].height &&tree[i].height<=max_height) maxh=tree[i].height;
    }
    
    
    
    //increase = tree[0].height-1;
    j=0;
    max_weight=0;
    qsort(tree,N,sizeof(gutuie),compare);
    //printf("maxH %i \n", maxh);
    //for(i=0;i<N;i++)
      //printf("%i %i \n", tree[i].height, tree[i].weight);
    for(i=tree[0].height;i<=max_height;i++)
    {
       while(i == tree[j].height){
         //Insert((0-tree[j].weight), H);
         coll.push_back (tree[j].weight);
         push_heap (coll.begin(), coll.end());
         j++;        
       }
       if(coll.size()>0){
          max_weight = max_weight + coll.front();
          pop_heap(coll.begin(), coll.end());
          coll.pop_back();
       }
    }  
    
    fprintf(fd,"%i",max_weight);
    
    fclose(fs);
    fclose(fd);
    
    //x = *(int*)cin;
    //getch();
    return 0;
    
}