Pagini recente » Cod sursa (job #2540081) | Cod sursa (job #1792532) | Cod sursa (job #1421342) | Cod sursa (job #49051) | Cod sursa (job #1431067)
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;
struct comp
{
bool operator() (const vector<int> & a,
const vector<int> & b)
{ return a[1] < b[1];}
} mycomp;
int best[100001];
int main()
{
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
int N;
f >> N;
vector<vector<int> > inte(N, vector<int> (2, 0));
for(int i = 0; i < N; i++)
{
int a, b;
f >> a >> b;
inte[i][0] = a;
inte[i][1] = b;
}
sort (inte.begin(), inte.end(), mycomp);
int j = 0;
best[0] = 0;
for(int i = 1; i <= inte[N - 1][1]; i++)
{
if (j == N)
{
best[inte[N - 1][1]] = best[i - 1];
break;
}
if(inte[j][1] < i)
{
j++;
i--;
continue;
}
else if (inte[j][1] > i)
{
best[i] = best[i - 1];
continue;
}
else
{
best[i] = max(best[i], best[i - 1]);
best[i] = max(best[i],
best[inte[j][0]] +
(inte[j][1] - inte[j][0]));
j++;
if (j == N)
{
best[inte[N - 1][1]] = best[i];
break;
}
if(inte[j][1] == i)
i--;
}
}
g << best[inte[N - 1][1]];
f.close();
g.close();
return 0;
}