Cod sursa(job #441073)

Utilizator _anonymousOnose Cristi _anonymous Data 12 aprilie 2010 19:04:28
Problema Gutui Scor 0
Compilator cpp Status done
Runda teme_upb Marime 2.19 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#include <sstream>
#include <string>
#include <map>
using namespace std;

typedef pair <int, int> Int_Pair;

int main()
{
 
	//salvez perechile inaltime - greutate intr-un multimap
	//pt a evita problema sortarii dupa inaltime
    multimap<int, int > gutui;
    multimap<int, int>::iterator it;
    multimap<int, int > rez;

    FILE *in,*out;
	in=fopen( "gutui.in","r" );
 	out=fopen( "gutui.out","w" );


    int i=0, j=0, x=0, k=0, y=0, max=0;;
    int N, H, U;
   	//citire N H U
    fscanf(in,"%d %d %d",&N,&H,&U);

	//citire si adaugare la multimap a perechilor inaltime- greutate din fisier
	for(i=0;i<N;i++)
    {
    fscanf(in,"\n%d %d",&y,&x);	
    gutui.insert ( Int_Pair ( y , x ) );
		
    	
    	
    }
    
int adaugat=0;

    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 ( it->first <=H )
        {        
            //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;
    }

    fprintf(out,"%d",max);
    fclose(in);
    fclose(out);
   
    return 0;
}