Pagini recente » Cod sursa (job #1001525) | Cod sursa (job #3281028) | Cod sursa (job #2323129) | Cod sursa (job #2959244) | Cod sursa (job #780232)
Cod sursa(job #780232)
#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;
}