Cod sursa(job #780232)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 20 august 2012 01:29:02
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb

#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>

typedef std::pair<unsigned int, unsigned int> concert; // end, start

int main (void)
{
	unsigned int n;
	std::ifstream input("heavymetal.in");
	input >> n;
	std::vector<concert> rock(n + 1);
	std::vector<concert>::iterator iterator(rock.begin());
	{
		std::vector<concert>::iterator end(&rock[n]);
		do
		{
			input >> iterator->second >> iterator->first;
			++iterator;
		}
		while (iterator < end);
	}
	input.close();
	rock[n] = std::make_pair(0,0);
	std::sort(rock.begin(),iterator);
	iterator = rock.begin();
	unsigned int last_concert(rock[n - 1].first);
	std::vector<unsigned int> best_time(last_concert + 1);
	unsigned int last_best(0), i(1), start, end, time;
	do
	{
		best_time[i] = last_best;
		if (iterator->first == i)
		{
			end = iterator->first;
			do
			{
				start = iterator->second;
				time = best_time[start] + end - start;
				if (best_time[i] < time)
					best_time[i] = time;
				++iterator;
				end = iterator->first;
			}
			while (end == i);
			last_best = best_time[i];
		}
		++i;
	}
	while (i <= last_concert);
	std::ofstream output("heavymetal.out");
	output << best_time[last_concert] << '\n';
	output.close();
	return 0;
}