Cod sursa(job #437920)

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

using namespace std;


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


typedef struct
{
unsigned int height;
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.height - v2.height);
}


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

int main()
{
unsigned int i,poz,nivel,cate,gata_nivel;
cell v[100000];
vector<unsigned int> myvector;
vector<unsigned int>::iterator it;


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].height,&v[i].value);
        v[i].nivel = 1 + (h - v[i].height)/u;
    }
fclose(fin);



   qsort(v,n,sizeof(cell),initialSort);


    for(poz = 0; poz< n; )
    {
        nivel = v[poz].nivel;
        gata_nivel = 0;

         for(i = poz; i< poz + nivel; i++)
         {
            if(v[i].nivel != nivel)
            {
                gata_nivel = 1;
                break;
            }

            cate = 0;

            for ( it=myvector.begin()  ; it < myvector.end(); it++)
            {
                if (v[i].value <= *it)
                {
                    cate ++;
                }
            }

            if( cate < v[i].nivel )
            {
                myvector.push_back(v[i].value);
                push_heap(myvector.begin(), myvector.end(),permaSort);
            }

            while(myvector.size() > v[i].nivel)
            {
                pop_heap(myvector.begin(), myvector.end(),permaSort);
                myvector.pop_back();
            }

         }
         if(!gata_nivel)
         {
             while(v[i].nivel == nivel)
             {
                 i++;
             }
         }
        poz = i;
    }


cate = 0;


for ( it=myvector.begin() ; it < myvector.end(); it++ )
{
cate += (*it);
}

fout = fopen("gutui.out","w");
fprintf(fout,"%i",cate);
fclose(fout);

return 0;
}