Pagini recente » Cod sursa (job #1300532) | Cod sursa (job #2072767) | Cod sursa (job #1092766) | Cod sursa (job #1472787) | Cod sursa (job #1430618)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int N;
int a[100002], b[100002], d[100000];
int bs(vector<pair<int, int>>& v, int a) {
int l = 0, r = N - 1;
int aux, currentMax = 0;
while (l <= r) {
int m = (l + r)/2;
if (v[m].second <= a && v[m].second > currentMax) {
currentMax = v[m].second;
aux = m;
}
if (a < v[m].second) {
r = m - 1;
}
else {
l = m + 1;
}
}
return aux;
}
int main()
{
fin >> N;
vector<pair<int, int>> v(N);
int m = 0;
for (int i = 0; i < N; i++) {
int x, y;
fin >> x >> y;
v[i] = make_pair(x, y);
}
sort(v.begin(), v.end(),
[](const pair<int,int>& p1, const pair<int, int>& p2) {
return p1.second < p2.second;
});
//cout << v[bs(v, 6)].second << endl;
d[0] = v[0].second - v[0].first;
for (int i = 1; i < N; i++) {
d[i] = max(d[i - 1], d[bs(v, v[i].first)] + v[i].second - v[i].first);
}
fout << d[N - 1] << endl;
}