Pagini recente » Cod sursa (job #464719) | Cod sursa (job #1845197) | Cod sursa (job #751041) | Cod sursa (job #2751329) | Cod sursa (job #2049878)
#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 100002
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct str{
int A, B;
bool operator < (const str& other) const{
if (B == other.B)
return A < other.A;
return B < other.B;
}
};
vector <str> C;
int n, best[MAXN];
inline void Read() {
int a, b;
fin >> n;
for (int i = 0; i < n; i++) {
fin >> a >> b;
C.push_back({a, b});
}
sort(C.begin(), C.end());
}
inline int search_(int N) {
int ii, step;
for (step = 1; step < N - 1; step <<= 1);
for (ii = 0; step; step >>= 1){
if (ii + step <= N - 1 && C[ii + step - 1].B <= C[N - 1].A)
ii += step;
}
return ii;
}
inline void DP() {
best[1] = C[0].B - C[0].A;
int poz;
for (int i = 2; i <= n; i++) {
best[i] = best[i - 1];
poz = search_(i);
best[i] = max(best[i - 1], best[poz] + C[i - 1].B - C[i - 1].A);
}
fout << best[n];
}
int main () {
Read();
DP();
fin.close(); fout.close(); return 0;
}