Cod sursa(job #674932)

Utilizator damgoodLincan Dan damgood Data 6 februarie 2012 21:45:42
Problema Lupul Urias si Rau Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <cstdio>
#include <set>

#define MAXN 100001

using namespace std;

int n, x, l;
int sum;

struct comp
{
	bool operator() (const pair<int,int> &left, const pair<int,int> &right)
	{
		if( left.first == right.first )
			return left.second < right.second;
		return left.first > right.first;
	}
};

multiset< pair<int,int>, comp > oi; 

void read()
{
	freopen("lupu.in", "r", stdin);
	freopen("lupu.out", "w", stdout);
	
	scanf("%d %d %d ", &n, &x, &l);
	int d, c;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d %d", &d, &c);
		oi.insert( make_pair(d, c) );
	}
}

void solve()
{
	int prevValue = 0;
	
	for(; x >= 0; x -= l)
	{
		int dist  = oi.begin()->first;
		int value = oi.begin()->second;
		while( dist > x )
		{
			if( prevValue < value )
			{
				sum = sum - prevValue + value;
				prevValue = value;
			}
			oi.erase( oi.begin() );
			dist  = oi.begin()->first;
			value = oi.begin()->second;
		}
		sum += value;
		prevValue = value;
	}
}

void printResult()
{
	printf("%d\n", sum);
}

int main()
{
	read();
	solve();
	printResult();
	return 0;
}