Cod sursa(job #441439)

Utilizator octavian.moraruOctavian Moraru octavian.moraru Data 12 aprilie 2010 22:11:50
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.58 kb
#include <iostream>

using namespace std;

struct Gutuie
{
    int inaltime;
    int greutate;
};

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

int main()
{

    int n,h,u;
    FILE *fin = fopen("gutui.in","r");
    FILE *fout = fopen("gutui.out","w");
    Gutuie* g;
    bool * final;

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

    g = (Gutuie *)malloc(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);
    }

    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 pozitie;

    for (int i = 0 ; i < n ; i++)
    {
        //cate gutui pot fi culese inaintea gutuii curente?
        pozitie = (h - g[i].inaltime)/u;
        for(int j = pozitie; j >= 0; j--)
        {
           //incercam sa ocupam chiar pozitia respectiva
           //daca este ocupata, cautam prima pozitie libera
            if(!final[j])
            {
                final[j] = true;
                total += g[i].greutate;
                //cout << g[i].greutate << ' ' << g[i].inaltime << ' ' << j <<'\n';
                break;
            }
        }
        //daca nu am gasit pozitie libera, gutuia nu mai poate fi culeasa

    }

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

    return 0;
}