Pagini recente » Cod sursa (job #1942162) | Cod sursa (job #1412612) | Cod sursa (job #1954977) | Cod sursa (job #2172557) | Cod sursa (job #906241)
Cod sursa(job #906241)
#include <cstdio>
#include <algorithm>
#define NMax 100005
using namespace std;
struct Interval{int left, right, profit;};
int N, DP[NMax];
Interval Int[NMax];
bool cmp (Interval X, Interval Y) {
return X.right < Y.right;
}
int BinSearch(int left, int right, int Val) {
int pos = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (Int[mid].right <= Val)
left = mid + 1, pos = mid;
else
right = mid - 1;
}
return pos;
}
void Solve() {
int i,j;
sort(Int + 1, Int + N + 1,cmp);
for (i = 1; i <= N; ++i) {
j = BinSearch(1, i - 1, Int[i].left);
DP[i] = max(DP[i - 1], DP[j] + Int[i].profit);
}
}
void Read() {
freopen("heavymetal.in", "r", stdin);
scanf("%d", &N);
for (int i = 1; i <= N; ++i) {
scanf("%d %d", &Int[i].left, &Int[i].right);
Int[i].profit=Int[i].right-Int[i].left;
}
}
void Print() {
freopen("heavymetal.out", "w", stdout);
printf("%d\n", DP[N]);
}
int main() {
Read();
Solve();
Print();
return 0;
}