Pagini recente » Cod sursa (job #2923661) | Cod sursa (job #345446) | Cod sursa (job #2848822) | Cod sursa (job #1785086) | Cod sursa (job #2629645)
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout("heavymetal.out");
#define cin fin
#define cout fout
bool cmp(pair < int , int > a, pair < int , int > b) {
return a.second <= b.second;
}
void cb(vector < pair < int, int > >a, int left, int right, int index, int &sol) {
while(left <= right) {
int mid = (left + right) / 2;
if(a[mid].second > a[index].first) {
right = mid - 1;
} else {
left = mid + 1;
sol = mid;
}
}
}
void solve() {
int n;
cin >> n;
vector < pair < int , int > > a(n + 1);
vector < int > dp(n + 1);
for(int i=1; i <= n; i++) {
cin >> a[i].first >> a[i].second;
}
/*
for(auto &it: a) {
cin >> it.first >> it.second;
}
*/
sort(a.begin() + 1, a.end(), cmp);
for(int i=1; i <= n; i++) {
int sol = 0;
cb(a, 0, i - 1, i, sol);
dp[i] = max(dp[i-1] , dp[sol] + a[i].second - a[i].first);
}
cout << dp[n];
}
int main() {
ios_base::sync_with_stdio(0);
cin .tie(0);
cout.tie(0);
int testCases = 1;
//cin >> testCases;
while(testCases--) {
solve();
}
}