Pagini recente » Cod sursa (job #301789) | Rating Diana Pop (diana.pop27) | Cod sursa (job #2358950) | Cod sursa (job #2346254) | Cod sursa (job #475101)
Cod sursa(job #475101)
#include <fstream>
#include <algorithm>
#include <utility>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n;
pair<int, int> v[100001];
int in[100001], t[100001];
bool cmp(int i1, int i2)
{
return v[i1].second <= v[i2].second;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; ++i)
{
fin >> v[i].first >> v[i].second;
in[i] = i;
}
sort(in + 1, in + n + 1, cmp);
int now = 0;
for (int i = 1; i <= n; ++i)
{
while (v[in[now + 1]].second <= v[in[i]].first)
++now;
t[in[i]] = max(t[in[i - 1]], t[in[now]] + v[in[i]].second - v[in[i]].first);
}
fout << t[in[n]];
fin.close();
fout.close();
}