Pagini recente » Cod sursa (job #3282984) | Cod sursa (job #1177498) | Cod sursa (job #1224892) | Cod sursa (job #1502257) | Cod sursa (job #2511698)
#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 f("heavymetal.in");
ofstream g("heavymetal.out");
int n;
f >> n;
vector<pair<int, int>> v(n + 1, make_pair(-1, -1));
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
f >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end());
for (int i = 1; i <= n; i++) {
int p = cb(v, 0, n, v[i].first);
dp[i] = max(dp[i - 1], v[i].second - v[i].first + dp[p]);
}
g << dp[n];
}