Cod sursa(job #439150)

Utilizator octavian.moraruOctavian Moraru octavian.moraru Data 11 aprilie 2010 13:31:09
Problema Gutui Scor 90
Compilator cpp Status done
Runda teme_upb Marime 2.44 kb
#include <iostream>
#include <list>

using namespace std;

struct Gutuie
{
    int inaltime;
    int greutate;
    bool ales;
};

bool myCompare( Gutuie g1, Gutuie g2 )
{
    if (g1.greutate == g2.greutate)
        return g1.inaltime > g2.inaltime;
    return g1.greutate > g2.greutate;
};

int main()
{
    //cout << "Hello world!" << endl;
    /*
    int A[] = {1, 4, 2, 8, 5, 7};
    const int N = sizeof(A) / sizeof(int);
    sort(A, A + N);
    for(int i = 0 ; i < N; i++)
        cout << A[i] << " ";
    */
    int n,h,u;
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    //Gutuie* g;

    //Gutuie* final;
    bool * final;

    fscanf(fin,"%d %d %d",&n,&h,&u);

    list<Gutuie> g;
    //g = (Gutuie *)malloc(sizeof(Gutuie) *n);
    //final = (Gutuie *)calloc(sizeof(Gutuie),n);
    final = (bool *)calloc(sizeof(bool),n);

    Gutuie aux;
    for (int i = 0 ; i < n ; i++)
    {
        fscanf(fin,"%d %d",&aux.inaltime,&aux.greutate);
        //g[i].ales = false;
        aux.ales = false;
        g.push_back(aux);
    }

    g.sort(myCompare);

   // for (int i = 0 ; i < n ; i++)
     //   cout << g[i].inaltime << ' ' << g[i].greutate << '\n';
    for (list<Gutuie>::iterator i = g.begin(); i != g.end(); i++)
        cout << (*i).inaltime << ' ' << (*i).greutate << '\n' ;



    cout << '\n';

    int total  = 0;
    //int u_curent = 0;
    //int prim = 0;
    //int rezervat = 0;
    //int maxh = 0;
    //int k = 0;
    int pozitie;
    //bool continua = true;
    //bool alestot = false;

    for (list<Gutuie>::iterator i = g.begin(); i != g.end(); i++)
    {
        /*
        if (g[i].ales || g[i].inaltime + u_curent > h)
        {
            //gutuia a depasit inaltimea maxima si nu mai poate fi culeasa
            //sau a fost deja aleasa
            //g[i].ales = true;
            continue;
        }*/
        pozitie = (h - (*i).inaltime)/u;
        for(int j = pozitie; j >= 0; j--)
            if(!final[j])
            {
                final[j] = true;
                total += (*i).greutate;
                (*i).ales = true;
                //u_curent += u;
                cout << (*i).greutate << ' ' << (*i).inaltime << ' ' << j <<'\n';
                i = g.erase(i);
                i--;
                break;
            }

    }

    fprintf(fout,"%d",total);
    fclose(fin);
    fclose(fout);

    return 0;
}