Cod sursa(job #434194)

Utilizator octavian.moraruOctavian Moraru octavian.moraru Data 5 aprilie 2010 12:17:23
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 2.2 kb
#include <iostream>

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;

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

    g = (Gutuie *)malloc(sizeof(Gutuie) *n);

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

    sort(g, g + n, myCompare);

    for (int i = 0 ; i < n ; i++)
        cout << g[i].inaltime << ' ' << g[i].greutate << '\n';

    cout << '\n';

    int total  = 0;
    int r = u;
    int prim;
    bool continua = true;
    bool alestot = false;
    while (continua)
    {
        continua = false;
        alestot = true;
        for (int i = 0 ; i < n ; i++)
        {
            if(g[i].inaltime + r - u > h)
                g[i].ales = true;
            if (!g[i].ales && alestot)
            {
                alestot = false;
                prim = i;
                //continue;
            }
            if(!g[i].ales && g[i].inaltime + r > h)
            {
                //gutuia nu poate fi aleasa la urmatoarea iteratie
                g[i].ales = true;
                total += g[i].greutate;
                r += u;
                continua = true;
                cout << g[i].greutate << ' ' << g[i].inaltime << '\n';
                break;
            }
        }
        if(!continua && !alestot)
        {
            g[prim].ales = true;
            total += g[prim].greutate;
            r += u;
            cout << g[prim].greutate << ' ' << g[prim].inaltime << '\n';
            continua = true;
        }

    }

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

    return 0;
}