Pagini recente » Cod sursa (job #561071) | Cod sursa (job #1269084) | Cod sursa (job #1854157) | Cod sursa (job #1212769) | Cod sursa (job #1967075)
#include <cstdio>
#include <algorithm>
using namespace std;
const int NMAX = 100005;
struct ABC
{
int st, dr;
};
ABC v[NMAX];
int st[NMAX];
long long int smax[NMAX];
long long int ssmax[NMAX];
bool cmp(ABC first, ABC second)
{
if(first.st == second.st)
return first.dr < second.dr;
return first.st < second.st;
}
int main()
{
int i, n, top;
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
scanf("%d", &n);
for(i = 0;i < n; ++i) {
scanf("%d%d", &v[i].st, &v[i].dr);
}
sort(v, v + n, cmp);
top = 1;
st[top] = 0;
smax[0] = v[0].dr - v[0].st;
ssmax[0] = smax[0];
for(i = 1;i < n; ++i) {
while(top > 0 && v[i].st < v[st[top]].dr) {
--top;
}
smax[i] = ssmax[st[top]] + v[i].dr - v[i].st;
ssmax[i] = max(ssmax[i - 1], smax[i]);
st[++top] = i;
}
printf("%lld\n", ssmax[n - 1]);
return 0;
}