Pagini recente » Cod sursa (job #929512) | Cod sursa (job #267033) | Cod sursa (job #2237660) | Cod sursa (job #2030275) | Cod sursa (job #2053369)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100002;
int n;
pair<int, int> band[MAXN];
int dp[MAXN];
void read() {
scanf("%d ", &n);
for (int i = 1; i <= n; i++) {
int x, y;
scanf("%d %d\n", &x, &y);
band[i] = { x, y };
}
}
int binSearch(int left, int right, int value) {
while (left < right) {
int middle = (left + right + 1) / 2;
if(band[middle].second <= value)
left = middle;
else right = middle - 1;
}
return left;
}
void solve() {
dp[1] = band[1].second - band[1].first;
for (int i = 2; i <= n; i++)
dp[i] = max(dp[i - 1], dp[binSearch(0, i, band[i].first)] + band[i].second - band[i].first);
printf("%d\n", dp[n]);
}
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
int main() {
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
read();
sort(band + 1, band + n + 1, cmp);
solve();
return 0;
}