Cod sursa(job #440153)

Utilizator _anonymousOnose Cristi _anonymous Data 11 aprilie 2010 22:21:05
Problema Gutui Scor 80
Compilator cpp Status done
Runda teme_upb Marime 2.97 kb
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <map>
using namespace std;

typedef pair <long, long> Int_Pair;

int main()
{

	//salvez perechile inaltime - greutate intr-un multimap
	//pt a evita problema sortarii dupa inaltime
    multimap<long, long, std::greater<long> > gutui;
    multimap<long, long>::iterator it;
    multimap<long, long > rez;

    ifstream in( "gutui.in" );
    ofstream out( "gutui.out" );
    string line;

    long v[3];
    long i=0, j=0, x=0, k=0, y=0, max=0;;
    long N, H, U;
	//citire N H U
    getline (in, line);
    string numar;
    for (i=0; i<=line.size(); i++)
    {
        if (line[i] != ' ' )  numar.push_back( line[i] );
        else
        {
            istringstream r( numar );
            r>>x;
            v[j] = x;
            numar.clear();
            j++;
        }
    }
    istringstream r( numar );
    r>>x;
    v[j] = x;
    numar.clear();
    N = v[0];
    H = v[1];
    U = v[2];

	//citire si adaugare la multimap a perechilor inaltime- greutate din fisier
    while (! in.eof() )
    {
        getline (in, line);
        for (i=0; i<=line.size(); i++)
        {
            if (line[i] != ' ' ) numar.push_back( line[i] );
            else
            {
                istringstream r( numar );
                r>>y;
                numar.clear();
            }

        }
        istringstream r( numar );
        r>>x;
        gutui.insert ( Int_Pair ( y, x ) );
        numar.clear();
        k++;
    }

//se parcurge multimap-ul cu key-le sortate (inaltimile in cazul nostru)
    for (it = gutui.begin();it != gutui.end();it++)
    {
        //daca inaltimea la care este gutuia este mai mica decat inalmimea maxima
        //la care poate ajunge gigel se culege
        if (H >= it->first )
        {
            //se adauga intr-un nou multimap (rez) si se scade din inaltimea
            //la care se poate ajunge inaltimea U (cu cat se ridica crengile dupa
            //fiecare gutuie culeasa)
            rez.insert( Int_Pair ( it->second, it->first ) );
            H=H-U;
        }
        else
        {
            //daca exista gutui culese si daca gutuia nu poate fi culeasa
            //se verifica daca exista o gutuie deja culeasa cu greutatea mai
            //mica decat a ei si se inlocuieste daca da
            if (!rez.empty())
                if ( it->second >= (rez.begin())->first )
                {
                    //avand in vedere ca rez este deja sortat se sterge gutuia
                    //usoara si se inlocuieste cu cea aleasa
                    rez.erase(rez.begin());
                    rez.insert( Int_Pair ( it->second, it->first ) );

                }
        }

    }

	//se calculeaza greutatea tuturor gutuilor culese
    for (it = rez.begin();it != rez.end();it++)
    {
        max += it->first;
    }

    out<<max;
    in.close();
    out.close();
    return 0;
}