Cod sursa(job #437814)

Utilizator VladTVlad Tudose VladT Data 10 aprilie 2010 02:48:15
Problema Gutui Scor 40
Compilator cpp Status done
Runda teme_upb Marime 1.39 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;
}quince;

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


long gutui()
{
  long N,H,U,left,total_weight=0,sum=0,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);
    total_weight+=q[i].weight;
  }
  fclose(in);
  if(!U)
        return total_weight;
  
  sort(q.begin(),q.end(),compare);
  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())
   {
    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;
}