Pagini recente » Cod sursa (job #2705830) | Cod sursa (job #2724184) | Cod sursa (job #1476117) | Cod sursa (job #2261169) | Cod sursa (job #519359)
Cod sursa(job #519359)
#include <fstream>
#include <algorithm>
using namespace std;
#define NMAX 100050
struct inter {
int x, y;
} V[NMAX];
int S[NMAX], mid, n, p, u, i, j;
bool cmp (inter a, inter b) {
return a.y < b.y;
}
int main () {
ifstream f ("heavymetal.in");
ofstream g ("heavymetal.out");
f >> n;
for (i = 1; i <= n; i++)
f >> V[i].x >> V[i].y;
sort (V + 1, V + 1 + n, cmp);
for (i = 1; i <= n; i++) {
p = 1, u = i - 1, j = 0;
while (p <= u) {
mid = (u - p) / 2 + p;
if (V[mid].y > V[i].x)
u = mid - 1;
else
p = mid + 1, j = mid;
}
S[i] = max (S[i-1], S[j] + V[i].y - V[i].x);
}
g << S[n];
f.close (); g.close ();
return 0;
}