Pagini recente » Cod sursa (job #1304701) | Cod sursa (job #372417) | Cod sursa (job #3203478) | Cod sursa (job #631237) | Cod sursa (job #1239820)
#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int nmax = 100005;
int n, l, r, m, i, j;
ll dp[nmax], sol;
struct interval
{
int x, y;
};
interval p[nmax];
struct cmp
{
bool operator () (interval a, interval b) const
{
return a.y < b.y;
}
};
int main()
{
freopen("heavymetal.in", "r", stdin);
freopen("heavymetal.out", "w", stdout);
scanf("%d", &n);
for(i = 1; i <= n; i++)
scanf("%d%d", &p[i].x, &p[i].y);
sort(p + 1, p + n + 1, cmp());
dp[1] = p[1].y - p[1].x;
sol = dp[1];
for(i = 2; i <= n; i++)
{
dp[i] = dp[i - 1];
l = 1;
r = i - 1;
while(l <= r)
{
m = (l + r) / 2;
if(p[m].y <= p[i].x)
{
j = m;
l = m + 1;
}
else
r = m - 1;
}
dp[i] = max(dp[i], dp[j] + p[i].y - p[i].x);
sol = max(sol, dp[i]);
}
printf("%lld\n", sol);
return 0;
}