Pagini recente » Cod sursa (job #3131630) | Cod sursa (job #2563607) | Cod sursa (job #2793357) | Cod sursa (job #834635) | Cod sursa (job #1744633)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int dp[100010];
pair<int, int> v[100010];
bool Compare(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int BinarySearch(int left, int right, int value) {
int answer = -1;
while (left <= right) {
int middle = (left + right) / 2;
if (v[middle].second <= value) {
answer = middle;
left = middle + 1;
}
else
right = middle - 1;
}
return answer;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i].first >> v[i].second;
sort(v + 1, v + n + 1, Compare);
for (int i = 1; i <= n; i++) {
int j = BinarySearch(1, n, v[i].first);
dp[i] = max(dp[i - 1], dp[j] + v[i].second - v[i].first);
}
cout << dp[n];
return 0;
}