Pagini recente » Cod sursa (job #120327) | Cod sursa (job #2689361) | Cod sursa (job #187685) | Cod sursa (job #3279366) | Cod sursa (job #3141970)
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 1e5;
pair<int, int> a[NMAX+5];
int dp[NMAX+5], n;
int Lower_bound(const int &value) {
int left = 1, right = n, ans = 0;
while (left <= right) {
int middle = (left+right)/2;
if (a[middle].second <= value)
ans = middle, left = middle+1;
else
right = middle-1;
}
return ans;
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int main() {
ios_base :: sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
fin>>n;
for (int i = 1; i <= n; i++)
fin>>a[i].first>>a[i].second;
sort(a+1, a+n+1, cmp);
for (int i = 1; i <= n; i++) {
int j = Lower_bound(a[i].first);
dp[i] = max(dp[i-1], dp[j]+(a[i].second-a[i].first));
}
fout<<dp[n];
return 0;
}