Cod sursa(job #435524)

Utilizator DonPushmeMilitaru Adrian DonPushme Data 7 aprilie 2010 15:51:02
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.5 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <vector>
#include <functional>

using namespace std;
typedef struct fruct{
        int greutate;
        int inaltime;       
}fruct;

int compare (const void * a, const void * b)
{
      return (  ((fruct*)a)->inaltime - ((fruct*)b)->inaltime );
}
int main(){
    FILE* f,*g;
    int j;
    f=fopen("gutui.in","rt");
    g=fopen("gutui.out","wt");
    int n,h,u;
    fscanf(f,"%d%d%d",&n,&h,&u);
    int interv=h/u;
    int height;
    fruct* v;
    v=(fruct*)malloc(100000*sizeof(fruct));
     
    int i;
    for(i=0;i<n;i++){
              fscanf(f,"%d%d\n",&height,&v[i].greutate);
              v[i].inaltime=(h-height)/u;          
    }
 
    qsort (v, n, sizeof(fruct), compare);
    
    priority_queue < int, vector<int>, greater<int> > minheap;
    int niv_curent;
    i=0;
    
    while(i<n){
            niv_curent=v[i].inaltime;
            while((niv_curent==v[i].inaltime)&&(i<n)){
                       minheap.push(v[i].greutate);
                       i++;
            }
            
            while((int)minheap.size()>niv_curent+1){
                   minheap.pop();
            }
            
                    
    }
    unsigned int s=0;
    while((int)minheap.size()>0){         
                     s+=(int)minheap.top();
                     minheap.pop();                      
    } 
    
    

    fprintf(g,"%d",s);
    fclose(f);
    fclose(g);
}