Cod sursa(job #437811)

Utilizator VladTVlad Tudose VladT Data 10 aprilie 2010 02:45:00
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <vector>
#define max(a,b) (a)<(b)?(b):(a)
using namespace std;



typedef struct{
        long weight;
        long height;
        long lifetime;
}quince;

bool compare (quince i,quince j) 
{ 
     return (i.height>j.height); 
}


long gutui()
{
  long N,H,U,left,total_weight,sum=0,limit,last;
  int i;

  
 
  FILE *in=fopen("gutui.in","r");
  fscanf(in,"%ld %ld %ld\n",&N,&H,&U);
  vector<quince> q (N);
  vector<long> heap;
  make_heap(heap.begin(),heap.end());

  for(i=0;i<N;i++)
  {
                  
   fscanf(in,"%ld %ld\n",&q[i].height,&q[i].weight);
   if(U)
        q[i].lifetime=(H-q[i].height)/U+1;
    total_weight+=q[i].weight;
    left+=q[i].lifetime;
    
  }
  //cout<<q.at(0).height;
  fclose(in);
  if(!U)
        return total_weight;
  
  sort(q.begin(),q.end(),compare);
 // for(i=0;i<N;i++)
     //   cout<<q[i].height<<endl;
  last=q.back().height;
  while((!q.empty()||heap.size())&&last<=H)
  {
   if(heap.size())
   {
    sum+=heap.front();
    pop_heap(heap.begin(),heap.end());
    heap.pop_back();
    last+=U;
   }
   else
   last=q.back().height;
   while(!q.empty())
   {
    //cout<<q.back().height;
    if(q.back().height>last+U)  
                             break;
     heap.push_back(q.back().weight);
     push_heap(heap.begin(),heap.end());
     q.pop_back();
    }                       
  }
  return sum;
}

int main ()
{
   FILE *out=fopen("gutui.out","w");
   fprintf(out,"%ld",gutui());
   fclose(out);  
  
  
  


  return 0;
}