Cod sursa(job #441075)

Utilizator _anonymousOnose Cristi _anonymous Data 12 aprilie 2010 19:05:31
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.43 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);

	
	for(i=0;i<N;i++)
    {
    fscanf(in,"\n%d %d",&y,&x);	
    gutui.insert ( Int_Pair ( (H-y)/U+1 , x ) );
		
    	
    	
    }
    
int adaugat=0;

    for (it = gutui.begin();it != gutui.end();it++)
    {     
        if ( it->first - adaugat >0 )
        {        
            rez.insert( Int_Pair ( it->second, it->first ) );
            adaugat++;
        }
        else
        {   
            if (!rez.empty())
                if ( it->second >= (rez.begin())->first )
                {
                    rez.erase(rez.begin());
                    rez.insert( Int_Pair ( it->second, it->first ) );

                }
        }

    }
    for (it = rez.begin();it != rez.end();it++)
    {
        max += it->first;
    }

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