Pagini recente » Cod sursa (job #1688612) | Cod sursa (job #2756602) | Cod sursa (job #185082) | Cod sursa (job #2423595) | Cod sursa (job #1368476)
#include <fstream>
#include <algorithm>
#define MAXN 100000
#define LOG 17
using namespace std;
struct formatie{
int A, B;
};
bool cmp(formatie x, formatie y) {
if (x.B < y.B || (x.B == y.B && x.A < y.A))
return true;
return false;
}
formatie v[MAXN + 1];
int D[MAXN + 1];
int bsearch(int right, int val) {
int p = 0, pas = (1 << LOG);
while (pas) {
int pos = p + pas;
if (pos <= right && v[pos].B <= val)
p = pos;
pas >>= 1;
}
if (v[p].B > val)
return -1;
return p;
}
int main () {
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
int n;
cin >> n;
for (int i = 0 ; i < n ; ++i)
cin >> v[i].A >> v[i].B;
sort(v, v + n, cmp);
D[0] = v[0].B - v[0].A;
for (int i = 1 ; i < n ; ++i) {
int p = bsearch(i - 1, v[i].A);
if (p == -1)
D[i] = v[i].B - v[i].A;
else
D[i] = (v[i].B - v[i].A) + D[p];
if (D[i] < D[i - 1])
D[i] = D[i - 1];
}
cout << D[n - 1];
return 0;
}