Pagini recente » Cod sursa (job #2021508) | Cod sursa (job #1858265) | Cod sursa (job #587032) | Cod sursa (job #1889005) | Cod sursa (job #1223825)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
#define nmax 100005
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
struct interval {
int x,y;
};
int n;
interval A[nmax];
int i;
int DP[nmax];
bool cmp(interval a, interval b) {
if (a.y == b.y) return a.x > b.x;
return a.y > b.y;
}
int bs(int x, int hi) {
int lo = 1;
while (lo <= hi) {
int mid = (hi + lo) >> 1;
if (A[mid].x >= x)
lo = mid + 1;
else
hi = mid - 1;
}
return DP[hi];
}
int main() {
in >> n;
for (i = 1; i <= n; i++)
in >> A[i].x >> A[i].y;
sort(A + 1, A + n + 1, cmp);
DP[1] = A[1].y - A[1].x;
for (i = 2; i <= n; i++)
DP[i] = max(DP[i-1], bs(A[i].y, i-1) + (A[i].y - A[i].x));
out << DP[n] << "\n";
return 0;
}