Cod sursa(job #437939)

Utilizator bmw-bavariaBavaria Motors bmw-bavaria Data 10 aprilie 2010 11:59:30
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.43 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;


FILE *fin,*fout;
unsigned int n,h,u;


typedef struct
{
unsigned int value;
unsigned int nivel;
}cell;


int initialSort(const void * a, const void * b)
{
    cell v1 = *((cell *)a);
    cell v2 = *((cell *)b);

    if(v1.nivel == v2.nivel) return -(v1.value - v2.value);
    return -(v1.nivel - v2.nivel);
}


bool permaSort(const int &a, const int &b) {
	return a >= b;
}

int main()
{
unsigned int i,max_nivel,sum =0;
int poz;
cell v[100000];
priority_queue<int> mypq;



fin = fopen("gutui.in","r");
fscanf(fin,"%i %i %i",&n,&h,&u);

    for(i=0; i<n; i++)
    {
        fscanf(fin,"%i %i",&v[i].nivel,&v[i].value);
        v[i].nivel = (h - v[i].nivel)/u;
    }
fclose(fin);


  qsort(v,n,sizeof(cell),initialSort);
/*
    for(i=0; i<n; i++)
    {
        printf("NIV = %i VAL = %i\n",v[i].nivel,v[i].value);
    }
*/
max_nivel = v[0].nivel;
i = 0;


 for (poz = max_nivel; poz >=0; poz--)
 {
      //printf("poz = %i\n",poz);
     while( (v[i].nivel == poz) && (i < n))
     {
         //printf("i = %i ",i);
         mypq.push(v[i].value);
         i++;
     }
     //printf("\n");
     if(!mypq.empty())
     {
         sum += mypq.top();
         mypq.pop();
     }
 }
fout = fopen("gutui.out","w");
fprintf(fout,"%i",sum);
fclose(fout);

return 0;
}