Cod sursa(job #441410)

Utilizator Emy21Filipescu Emilian Emy21 Data 12 aprilie 2010 21:54:47
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 1.75 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 sortare(gut x,gut y){
   return ( x.interval<y.interval );
 };



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;
  
   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++;
     v.push_back(g);
   }
   stable_sort(v.begin(),v.end(),sortare);
   
   for (i=0; i<v.size(); i++){
     cout << v[i].greutate << " " << v[i].interval << endl;
   }

   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){
       printf("greu %d\n",v[i].greutate);
       minheap.push(v[i].greutate);
       i++;
     }
       else {
 	while(minheap.size() > rang) 
 	  minheap.pop();
 	  
 	rang=v[i].interval;
       }
       printf("size=%d ",minheap.size());
   }
  
  while(minheap.size() > rang) 
	  minheap.pop();
  
  while(minheap.size() > 0) {
    max = max + minheap.top();
    minheap.pop();
  }
  
  fprintf(out,"%d",max);
  
return 0;
}