Cod sursa(job #439485)

Utilizator MirceaMMircea Muscalu MirceaM Data 11 aprilie 2010 16:33:50
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 1.8 kb
#include <stdio.h>
#include <stdlib.h>
//#include <conio.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct{
  int a,b;
} gutuie;

int comp(const void *a, const void *b){
    gutuie x=*(gutuie*)a;
    gutuie y=*(gutuie*)b;
    
    if(x.a>y.a) return -1;
    if(x.a==y.a) return (x.b-y.b);
    return 1;
    
}



int main(){
    
    int i,n,k,h,p,u,max=0,nc;
    gutuie x[100000];
    
    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);
    
    qsort(&x,n,sizeof(gutuie),comp);
    
   // for(i=0;i<n;i++)
   //   printf("%i %i\n",x[i].a,x[i].b);
    
    
     vector<int> v(100000);
    
    p=x[0].a;
    nc=p;
    for(i=0;i<n;i++)
    {
    //  printf("\nnr:%i",x[i].b);
      if(p!=x[i].a) 
         {
         pop_heap(v.begin(),v.end());
         max+=v.back();
         nc--;
         p=x[i].a;
        if(x[i].a<0) break;
     //    printf("->m:%i ",v.back());
         v.pop_back();
   //    printf("ad:%i ",x[i].b);
         v.push_back(x[i].b);   
         push_heap(v.begin(),v.end());
         
         }
       else{
      //  printf("ad:%i ",x[i].b);
         v.push_back(x[i].b);   
         push_heap(v.begin(),v.end());
       }
       if(nc==-1) break;
    }
    
   while(p>=0){
         pop_heap(v.begin(),v.end());
         max+=v.back();
   //      printf("->m:%i ",v.back());
         v.pop_back(); 
         p--;     
    }
    
      
//    printf("\n%i\n",max);
    
    f = fopen("gutui.out","wt");
    fprintf(f,"%i",max);
    fclose(f);
    
    
  /* getch();*/
    return 0;
}