Cod sursa(job #449025)

Utilizator darrenRares Buhai darren Data 5 mai 2010 13:01:08
Problema Lupul Urias si Rau Scor 68
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

typedef unsigned long long uint64;

struct sheep
{
	uint64 a, d;
	uint64 t;
};
sheep make_sheep( uint64 d, uint64 a )
{
	sheep aux;
	aux.a = a, aux.d = d;
	return aux;
}
bool cmp( const sheep& s1, const sheep& s2 )
{
	return s1.a > s2.a;
}

void read();
void write();
void greedy();

uint64 n, x, l, mx;
vector<sheep> s;
bool t[100005];

int main()
{
	read();
	greedy();
	write();
	return 0;
}

void read()
{
	ifstream fin( "lupu.in" );
	fin >> n >> x >> l;
	uint64 d, a;
	for ( uint64 i = 0; i < n; ++i )
	{
		fin >> d >> a;
		s.push_back( make_sheep( d, a ) );
		s[i].t = ( x - s[i].d ) / l;
	}
	fin.close();
}

void write()
{
	ofstream fout( "lupu.out" );
	fout << mx;
	fout.close();
}

void greedy()
{
	sort( s.begin(), s.end(), cmp );
	uint64 p = 0, ps = 0;
	while ( ps < s.size() )
	{
		for ( int i = s[ps].t; i >= 0; --i )
			if ( t[i] == false )
			{
				t[i] = true;
				mx += s[ps].a;
				break;
			}
		++ps;
		p += l;
	}
}