Cod sursa(job #539037)

Utilizator iconiKMircea Chirea iconiK Data 22 februarie 2011 11:44:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

struct band
{
	int x, y;

	band() : x(0), y(0) { }

	bool operator<(const band &b) const
	{
		return (y < b.y);
	}
};

int main()
{
	ifstream in("heavymetal.in");

	int N;
	in >> N;
	
	vector<band> b(N + 1);

	for (int i = 1; i <= N; i++)
		in >> b[i].x >> b[i].y;

	sort(b.begin(), b.end());

	int Tmax = b.back().y;
	vector<int> best(Tmax + 1, 0);

	for (int i = 1; i <= Tmax; i++)
	{
		best[i] = best[i - 1];

		for (int j = 1; b[j].y == i; j++)
			best[i] = max(best[i], best[b[j].x] + (b[j].y - b[j].x));
	}

	ofstream out("heavymetal.out");
	out << best[Tmax];
}