Pagini recente » Cod sursa (job #1513492) | Cod sursa (job #2787967) | Cod sursa (job #3189491) | Cod sursa (job #242129) | Cod sursa (job #539037)
Cod sursa(job #539037)
#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];
}