Cod sursa(job #439098)

Utilizator octavian.moraruOctavian Moraru octavian.moraru Data 11 aprilie 2010 12:56:46
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 2.11 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;
    //Gutuie* final;
    bool * final;

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

    g = (Gutuie *)malloc(sizeof(Gutuie) *n);
    //final = (Gutuie *)calloc(sizeof(Gutuie),n);
    final = (bool *)calloc(sizeof(bool),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 u_curent = 0;
    //int prim = 0;
    //int rezervat = 0;
    //int maxh = 0;
    //int k = 0;
    int pozitie;
    //bool continua = true;
    //bool alestot = false;

    for (int i = 0 ; i < n ; 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 - (g[i].inaltime + u_curent))/u;
        for(int j = pozitie; j >= 0; j--)
            if(!final[j])
            {
                final[j] = true;
                total += g[i].greutate;
                g[i].ales = true;
                //u_curent += u;
                cout << g[i].greutate << ' ' << g[i].inaltime << ' ' << j <<'\n';
                break;
            }

    }

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

    return 0;
}