Cod sursa(job #441457)

Utilizator Emy21Filipescu Emilian Emy21 Data 12 aprilie 2010 22:22:09
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2 kb
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> 
using namespace std;

class gut{
  public:
    int interval;
    int greutate;
};

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




bool operator<(const gut &x,const gut &y){
   return ( x.interval<y.interval );
 }

// bool operator<(const Thread &a, const Thread &b)
// {
//   return a.getpriority() < b.getpriority();
// }


int main(){
  FILE *in=fopen("gutui.in","rt");
  FILE *out=fopen("gutui.out","wt");
  int n,h,u;
  int inaltime;
  int greu;
  int i,rang,max = 0;
  fscanf(in,"%d %d %d",&n,&h,&u);
  vector<gut> v;
  gut g;
  
  
   
  
   priority_queue<int,vector<int>,mycomparison> minheap;
   priority_queue<gut> v1;
   for (i = 0;i < n;i++){
     fscanf(in,"%d %d",&inaltime,&greu);
     g.greutate=greu;
     g.interval = (h - inaltime) / u;
     if (g.interval >= 0) 
       g.interval++;
     g.interval=-g.interval;
     v1.push(g);
   }

   i=0;
   gut temporar;
   temporar=v1.top();
   //pozitionare pe prima gutuie disponibila (interval pozitiv)
    while(temporar.interval >0) {
      v1.pop();
     i++;
    }
    
   temporar=v1.top();
   rang = -temporar.interval;
   printf("**rang=%d ",rang);
   while (i < n){
     temporar=v1.top();
     temporar.interval=-temporar.interval;
     if (temporar.interval == rang){
       printf("greu %d\n",temporar.greutate);
       minheap.push(temporar.greutate);
       i++;
       v1.pop();
     }
       else {
 	while(minheap.size() > rang) 
 	  minheap.pop();
 	  
 	rang=temporar.interval;
       }
       printf("rang=%d ",rang);
   }
  
  while(minheap.size() > rang) 
	  minheap.pop();
  
  while(minheap.size() > 0) {
    max = max + minheap.top();
    minheap.pop();
  }
  
  fprintf(out,"%d",max);
  
return 0;
}