Pagini recente » Cod sursa (job #2854986) | Cod sursa (job #2499275) | Cod sursa (job #2428706) | Cod sursa (job #2920989) | Cod sursa (job #2511684)
#include <bits/stdc++.h>
using namespace std;
typedef pair<int64_t,int64_t> pii;
const int64_t MAXN = 1000010;
int64_t N;
int64_t dp[MAXN];
vector<pii> arr;
int main(){
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin >> N;
arr.resize(N);
for (int64_t i = 0; i < N; i++)
fin >> arr[i].first >> arr[i].second;
sort(arr.begin(), arr.end(), [](const pii &a, const pii &b) {
return a.second < b.second;
});
dp[0] = arr[0].second - arr[0].first;
int64_t ans = 0;
for (int64_t i = 1; i < N; i++) {
int64_t mx = 0;
int64_t left = 0, right = i - 1, ans = left - 1;
while (left <= right) {
int64_t mid = (left + right) / 2;
if (arr[mid].second <= arr[i].first) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
if (ans >= 0) {
mx = dp[ans];
}
dp[i] = max(dp[i - 1], mx + arr[i].second - arr[i].first);
}
fout << dp[N - 1];
return 0;
}