Pagini recente » Cod sursa (job #896119) | Cod sursa (job #242369) | Cod sursa (job #2859710) | Cod sursa (job #2500659) | Cod sursa (job #1223249)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100003;
struct band {
int left, right;
};
bool operator < (const band &a, const band &b) {
if (a.right < b.right)
return 1;
if (a.right == b.right)
return a.left < b.left;
return 0;
}
band V[NMAX];
int sel[NMAX], D[NMAX];
int binarySearch (int right, const int &val) {
int left = 1, middle;
while (left <= right) {
middle = left + right >> 1;
if (val < V[middle].right)
right = middle - 1;
else
left = middle + 1;
}
return right;
}
int main () {
freopen ("heavymetal.in", "r", stdin);
freopen ("heavymetal.out", "w", stdout);
int N, i, j, k;
scanf ("%d", &N);
for (i = 1; i <= N; ++i)
scanf ("%d%d", &V[i].left, &V[i].right);
sort (V + 1, V + N + 1);
for (i = 1; i <= N; ++i) {
k = binarySearch (i - 1, V[i].left);
D[i] = max (D[i - 1], D[binarySearch (i - 1, V[i].left)] + V[i].right - V[i].left);
}
printf ("%d", D[N]);
}