Cod sursa(job #539053)

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

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

	int N, Tmax = 0;
	in >> N;
	
	vector<vector<int>> v(1 << 17);

	for (int i = 1; i <= N; i++)
	{
		int x, y;
		in >> x >> y;

		v[y].push_back(x);
		Tmax = max(Tmax, y);
	}

	vector<int> best(1 << 17, 0);

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

		for (int j = 0; j < (int) v[i].size(); j++)
			best[i] = max(best[i], best[v[i][j]] + i - v[i][j]);
	}

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