Pagini recente » Cod sursa (job #2526825) | Cod sursa (job #1401836) | Cod sursa (job #2121123) | Cod sursa (job #3133646) | Cod sursa (job #2511686)
#include <bits/stdc++.h>
using namespace std;
int cb(vector<pair<int, int>> &v, int l, int r, int x) {
int ans = -1;
while (l <= r) {
int m = (l + r) / 2;
if (v[m].second <= x) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main()
{
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n;
cin >> n;
vector<pair<int, int>> v(n, make_pair(0, 0));
vector<int> dp(n, 0);
for (int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
int p = cb(v, 0, n - 1, v[i].first);
if (p != -1) {
dp[i] = max(dp[i - 1], v[i].second - v[i].first + dp[p]);
} else {
dp[i] = max(dp[i - 1], v[i].second - v[i].first);
}
}
cout << dp[n - 1];
}