Pagini recente » Cod sursa (job #471818) | Cod sursa (job #1710439) | Cod sursa (job #1382866) | Cod sursa (job #2155246) | Cod sursa (job #1796845)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 100003
struct str
{
int x, y;
};
bool cmp (str a, str b)
{
return a.y < b.y;
}
using namespace std;
str v[NMAX];
int n, d[NMAX];
int main ()
{
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
cin >> n;
for (int i = 1; i <= n ;i++)
{
cin >> v[i].x >> v[i].y;
}
sort (v + 1, v + 1 + n, cmp);
for (int i = 1; i <= n; i++)
{
int l1 = 1;
int sol = 0;
int l2 = i - 1;
while (l1 <= l2)
{
int mid = (l1 + l2) / 2;
if (v[i].x < v[mid].y)
{
l2 = mid - 1;
}
else
{
l1 = mid + 1;
sol = mid;
}
}
d[i] = max (d[i - 1], d[sol] + v[i].y - v[i].x);
}
cout << d[n];
return 0;
}