Cod sursa(job #793415)

Utilizator cristianalex81Cristian Alexandru cristianalex81 Data 2 octombrie 2012 21:12:58
Problema Gutui Scor 50
Compilator cpp Status done
Runda teme_upb Marime 1.32 kb
#include <stdlib.h>
#include <fstream>
#define dim 100005
using namespace std;

struct gut
{
    int i;
    int g;
};

int compare (const void *a, const void *b)
{
    return (*(gut*)b).i - (*(gut*)a).i;
}

gut pom[dim];
gut sol[dim];
int n,h,u,ct;

gut* worst_node()
{
    int index = 0;
    for(int i=1;i<ct;i++)
        if(sol[i].g<sol[index].g)
            index = i;
    return &sol[index];
}

int main()
{
    ifstream cin("gutui.in");
    ofstream cout("gutui.out");

    cin>>n>>h>>u;
    for(int i=0;i<n;i++)
        cin>>pom[i].i>>pom[i].g;
    qsort(pom,n,sizeof(gut),compare);
    for(int i=0;i<n;i++)
    {
        if (pom[i].i<h)//nodu poate fi ajuns;
        {
            sol[ct]=pom[i];//adaug la sol
            ct++;
            h-=u;//scade distanta
        }
        else//verific daca poate imbunatati solutia
        {
            if(ct>0)//if there is anything to check with
            {
                gut *min = worst_node();//index of the worste node in solution
                if((*min).g<pom[i].g)//my node is better
                {
                    (*min).g=pom[i].g;
                    (*min).i=pom[i].i;
                }

            }
        }
    }
    int t=0;
    for(int i=0; i<ct;i++)
        t+=sol[i].g;
    cout<<t;
    return 0;
}