Cod sursa(job #435720)

Utilizator bmw-bavariaBavaria Motors bmw-bavaria Data 7 aprilie 2010 19:57:43
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.79 kb
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;


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


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


int compare (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);
}


int main()
{
int i,poz,max_nivel = 0,cate;
cell v[100000];
int s = 0;
vector<int> myvector;
vector<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),compare);

/*
     for(i=0; i<n; i++)
    {
        printf("%i %i %i\n",v[i].height,v[i].value,v[i].nivel);
    }

max_nivel = v[i-1].nivel;
*/

    for(i = 0; i< n; i++)
    {
         if((i == 0) || (v[i].nivel > v[i-1].nivel) )
         {
             myvector.push_back(v[i].value);
         }
         else
         {
            cate = 0;

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

                if(v[i].value > *it)
                {
                    myvector.erase(it);
                }
                else
                {
                    cate ++;
                }
            }

            if( cate < v[i].nivel )
            {
                myvector.push_back(v[i].value);
            }
         }

    }

cate = 0;

for ( it=myvector.begin() ; it != myvector.end(); it++ )
{
//printf("%i ",(*it));
cate += (*it);
}

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

return 0;
}