Pagini recente » Cod sursa (job #2806532) | Cod sursa (job #3277930) | Cod sursa (job #1518419) | Cod sursa (job #2251609) | Cod sursa (job #1731971)
#include <cstdio>
#include <algorithm>
using namespace std;
int d[100005];
struct MIHU{
int x, y;
}v[100005];
int bs(int st, int dr, int capat){
int med, last = -1;
while (st <= dr){
med = (st + dr) / 2;
if (v[med].y <= capat){
last = med;
st = med + 1;
}
else
dr = med - 1;
}
return last;
}
bool cmp(MIHU a, MIHU b){
return a.y < b.y;
}
int main(){
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
int n, x, y, i, j, max1 = 0;
scanf("%d", &n);
for (i = 1; i <= n; i ++){
scanf("%d%d", &x, &y);
v[i].x = x;
v[i].y = y;
}
sort(v + 1, v + n + 1, cmp);
for (i = 1; i <= n; i ++){
j = bs(1, n, v[i].x);
d[i] = max(d[i - 1], d[j] + v[i].y - v[i].x);
if (max1 < d[i])
max1 = d[i];
}
printf("%d\n", max1);
}