Cod sursa(job #680227)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 15 februarie 2012 00:01:05
Problema Gutui Scor 100
Compilator cpp Status done
Runda teme_upb Marime 1.96 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Quince
{
	Quince() :
		h(0),
		w(0)
	{}

	Quince(const long long hh, const long long ww) :
		h(hh),
		w(ww)
	{}
    
    bool operator < (const Quince& q) const
    {
        return w > q.w;
    }

	long long h;
	long long w;
};

struct CompareByPickTime
{
	CompareByPickTime(const long long hh, const long long uu) :
		u(uu),
		h(hh)
	{}
	
	bool operator() (const Quince& q1, const Quince& q2) const
	{
		long long h1 = (h-q1.h)/u;
		long long h2 = (h-q2.h)/u;
		
		if (h1 == h2)
		{
			return q1.w > q2.w;
		}
		
		return h1 < h2;
	}
	
	long long u;
	long long h;
};


int main()
{
	long long n, h, H, u;
	vector<Quince> vQuinces;
	fstream fin("gutui.in", fstream::in);
	fstream fout("gutui.out", fstream::out);
	
	fin >> n >> h >> u;
    H = h;
	//cout << n << " " << h << " " << u << endl;
	
	for (int i=0; i<n; ++i)
	{
		long long h,w;
		fin >> h >> w;
		
		vQuinces.push_back(Quince(h,w));
		
		//cout << h << " " << w << endl;
	}
	
	//cout << endl;
	
	CompareByPickTime comp(h,u);
	sort(vQuinces.begin(), vQuinces.end(), comp);
	
	/*for (int i=0; i<n; ++i)
	{
		cout << vQuinces[i].h << " " << vQuinces[i].w << " " << (h-vQuinces[i].h)/u << endl;
	}*/
	
	unsigned long long totalWeight = 0;
    priority_queue<Quince> Q;
	
	for (int i=0; i<n; ++i)
	{
		if (h >= vQuinces[i].h)
		{
            Q.push(vQuinces[i]);
			
			h -= u;
		}
        else
        {
            if (vQuinces[i].h <= H)
            {
                if (Q.top().w < vQuinces[i].w)
                {
                    Q.pop();
                    Q.push(vQuinces[i]);
                }
            }
        }
	}
    
    while (!Q.empty())
    {
        totalWeight += Q.top().w;
        Q.pop();
    }
	
	fout << totalWeight << endl;
	
	fin.close();
	fout.close();
	return 0;
}