Cod sursa(job #680087)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 14 februarie 2012 08:24:55
Problema Gutui Scor 10
Compilator cpp Status done
Runda teme_upb Marime 1.58 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint32;
typedef unsigned long long uint64;

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

	Quince(const uint32 hh, const uint32 ww) :
		h(hh),
		w(ww)
	{}

	uint32 h;
	uint32 w;
};

struct CompareByPickTime
{
	CompareByPickTime(const uint32 hh, const uint32 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;
	}
	
	uint32 u;
	uint32 h;
};


int main()
{
	int n, h, u;
	vector<Quince> vQuinces;
	fstream fin("gutui.in", fstream::in);
	fstream fout("gutui.out", fstream::out);
	
	fin >> n >> h >> u;
	//cout << n << " " << h << " " << u << endl;
	
	for (int i=0; i<n; ++i)
	{
		uint32 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;
	}*/
	
	long long totalWeight = 0;
	long long prev = -1;
	
	for (int i=0; i<n; ++i)
	{
		const long long val = h - (long long)vQuinces[i].h;
		if (val >= 0L)
		{	
			totalWeight += vQuinces[i].w;
			
			h -= u;
			
			prev = h-vQuinces[i].h;
		}
	}
	
	fout << totalWeight << endl;
	
	fin.close();
	fout.close();
	return 0;
}