Cod sursa(job #449007)

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

struct sheep
{
	int a, d;
};
sheep make_sheep( int d, int 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();

int n, x, l, mx;
vector<sheep> s;

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

void read()
{
	ifstream fin( "lupu.in" );
	fin >> n >> x >> l;
	int d, a;
	for ( int 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 );
	int p = 0, ps = 0;
	while ( ps < s.size() )
	{
		while ( s[ps].d + p > x && ps < s.size() )
			++ps;
		if ( ps == s.size() )
			break;
		
		mx += s[ps].a;
		++ps;
		
		p += l;
	}
}