Cod sursa(job #439832)

Utilizator Emy21Filipescu Emilian Emy21 Data 11 aprilie 2010 19:41:20
Problema Gutui Scor 30
Compilator cpp Status done
Runda teme_upb Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

typedef struct gutuie{
  int interval;
  int g;
}gutuie;

class mycomparison{
  public:
  bool operator() (const int& a, const int& b) const{
    return (a>b);
  } 
};

int sortare(const void * x,const void * y){
  return ( *(int*)x - *(int*)y );
};



int main(){
  FILE *in=fopen("gutui.in","rt");
  FILE *out=fopen("gutui.out","wt");
  int n,h,u;
  int inaltime;
  int i,j,rang,max=0;
  gutuie v[1000];
  fscanf(in,"%d %d %d",&n,&h,&u);
  
  priority_queue< int, vector<int>, mycomparison > minheap;
 
  for (i=0;i<n;i++){
    fscanf(in,"%d %d",&inaltime,&v[i].g);
    v[i].interval=(h-inaltime)/u;
  }
  for (i=0;i<n;i++)
    if (v[i].interval>=0) v[i].interval++;
  
  qsort(v,n,sizeof(gutuie),sortare);
     
  for (i=0;i<n;i++)
      printf("interval=%d greutate=%d \n",v[i].interval,v[i].g);
  
  i=0;
  while(v[i].interval<0) i++;
  
  rang=v[i].interval;
  
  while (i<n){
    if (v[i].interval==rang){
      minheap.push(v[i].g);
      i++;
    }
      else {
	while(minheap.size()>rang) 
	  minheap.pop();
	  
	rang=v[i].interval;
      }
  }
  
  while(minheap.size()>0) {
    max=max+minheap.top();
    minheap.pop();
  }
  
  fprintf(out,"%d",max);
  
return 0;
}