Pagini recente » Cod sursa (job #508168) | Cod sursa (job #2100495) | Cod sursa (job #2044193) | Cod sursa (job #715041) | Cod sursa (job #2987990)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int n;
pair <int, int> a[100005];
bool cmp (pair <int, int> a, pair <int, int> b) {
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int CB (int val) {
int st = 1, dr = n, mid, p = 0;
while (st <= dr) {
int mid = (st + dr) / 2;
if (a[mid].second <= val) {
p = mid;
st = mid + 1;
}
else dr = mid - 1;
}
return p;
}
long long dp[100005];
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1, cmp);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1];
int j = CB(a[i].first);
dp[i] = max(dp[i], dp[j] + a[i].second - a[i].first);
}
fout << dp[n] << "\n";
return 0;
}