Cod sursa(job #440007)

Utilizator Emy21Filipescu Emilian Emy21 Data 11 aprilie 2010 21:22:01
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.43 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
using namespace std;

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

//pentru transformarea priority_queue in minheap
class mycomparison{
  public:
  bool operator() (const int& a, const int& b) const{
    return (a > b);
  } 
};

//pentru qsort
int sortare(const void * x,const void * y){
  gutuie *temp1=(gutuie*)x;
  gutuie *temp2=(gutuie*)y;
  return ( temp1->interval - temp2->interval );
};



int main(){
  FILE *in=fopen("gutui.in","rt");
  FILE *out=fopen("gutui.out","wt");
  int n,h,u;
  int inaltime;
  int i,rang,max = 0;
  gutuie v[110000];
  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);
     
  i=0;
  //pozitionare pe prima gutuie disponibila (interval pozitiv)
  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() > rang) 
	  minheap.pop();
  
  while(minheap.size() > 0) {
    max = max + minheap.top();
    minheap.pop();
  }
  
  fprintf(out,"%d",max);
  
return 0;
}