Pagini recente » Cod sursa (job #2264582) | Cod sursa (job #729542) | Cod sursa (job #1385603) | Cod sursa (job #2827330) | Cod sursa (job #2048378)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
#define pii pair<int, int>
#define x first
#define y second
const int Nmax = 100000 + 5;
#define ll long long
ll n, maxim, dp[Nmax];
pii p[Nmax];
bool cmp(pii a, pii b)
{
if(a.y == b.y)return a.x < b.x;
return a.y < b.y;
}
int main()
{
fin >> n;
for(int i = 1; i <= n; ++i)
fin >> p[i].x >> p[i].y;
sort(p +1 , p + n + 1);
dp[1] = p[1].y - p[1].x;
for(int i = 2, st, dr; i <= n; ++i)
{
st = 0; dr = i;
while(dr - st > 1)
{
int mid = st + (dr - st) /2;
if(p[mid].y <= p[i].x)st = mid;
else dr = mid;
}
if(st == 0)dp[i] = p[i].y - p[i].x;
else dp[i] = dp[st] + p[i].y - p[i].x;
if(dp[i] > maxim)maxim = dp[i];
}
fout << maxim;
return 0;
}