Cod sursa(job #449009)

Utilizator darrenRares Buhai darren Data 5 mai 2010 12:36:47
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

typedef unsigned long long uint64;

struct sheep
{
	uint64 a, d;
};
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;

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;
		if ( d <= x )
			s.push_back( make_sheep( d, a ) );
	}
	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 ( true )
	{
		while ( s[ps].d + p > x && ps < s.size() )
			++ps;
		if ( ps == s.size() )
			break;
		
		mx += s[ps].a;
		++ps;
		
		p += l;
	}
}