Cod sursa(job #441542)

Utilizator tartacutza90Tiberiu Georgescu tartacutza90 Data 12 aprilie 2010 23:02:30
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.33 kb
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> hip;
vector<int>::iterator it;

FILE *fin,*fout;
int n,u,h;
typedef struct {int val,alt;}gutuie;
gutuie v[100000];

int f(const void *a,const void *b)
{
  gutuie x,y;
  x=(*(gutuie *)a);
  y=(*(gutuie *)b);
  if(x.alt > y.alt)return -1;
   if(x.alt < y.alt)return 1;
    else 
    {
     if( x.val > y.val)return -1;
       return 1;
    }
}

int Hmax(int x)
{
  int k=0,j=h-x;
  if(j<0)return j;
   else 
      while(j-u>=0)
        {
          j-=u;
          k++;
        }
  return k+1;
}

int main()
{
    fin=fopen("gutui.in","rt");
    fout=fopen("gutui.out","wt");
    int sol=0;
    fscanf(fin,"%i %i %i",&n,&h,&u);
    for(int i=0;i<n;i++)
     {
       fscanf(fin,"%i %i",&v[i].alt,&v[i].val);
       v[i].alt=Hmax(v[i].alt);
      } 
     qsort(v,n,sizeof(gutuie),f);
   int j=0;
   for(int k=v[0].alt;k>=1;k--)
    { 
      while (v[j].alt == k && j<n)
      {
        hip.push_back(v[j].val);
        push_heap(hip.begin(),hip.end());
        j++;
      }
     if(!hip.empty())
      {
       pop_heap(hip.begin(),hip.end());
       sol+=hip.back();
       hip.pop_back();
       } 
     }
    fprintf(fout,"%i",sol);
    fclose(fin);
    fclose(fout);
    
}