Cod sursa(job #439927)

Utilizator MirceaMMircea Muscalu MirceaM Data 11 aprilie 2010 20:35:29
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.19 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct{
  int a,b;
} gutuie;
/*functie de comparare pt qsort*/
int comp(const void *a, const void *b){
    gutuie x=*(gutuie*)a;
    gutuie y=*(gutuie*)b;
    
    return -x.a+y.a;
}



int main(){
    
    int i,n,h,p,u,max=0;
    gutuie x[100000];
    
    /*citire date*/
    
    FILE *f = fopen("gutui.in","rt");
    fscanf(f,"%i %i %i\n",&n,&h,&u);
    
    for(i=0;i<n;i++)
    {
       fscanf(f,"%i %i\n",&x[i].a,&x[i].b);
       if(u!=0)
       if(x[i].a>h) x[i].a=-1;
       else x[i].a=(h-x[i].a)/u;
    }
    fclose(f);
    
    /*sortare*/
    qsort(&x,n,sizeof(gutuie),comp);   
    
    /*algoritm*/   
    vector<int> v(100000);
    i=0;
    for(p=x[0].a;p>=0;p--)
    {
      while(x[i].a==p && i<n)
      {
         v.push_back(x[i].b);   
         push_heap(v.begin(),v.end()); 
         i++;         
      }
   
       pop_heap(v.begin(),v.end());
       max+=v.back();
       v.pop_back();
    }
    
    /*scriere rezultat*/
    f = fopen("gutui.out","wt");
    fprintf(f,"%i",max);
    fclose(f);
    
    return 0;
}