Pagini recente » Monitorul de evaluare | Cod sursa (job #2353232) | Cod sursa (job #532652) | Cod sursa (job #230543) | Cod sursa (job #2048386)
#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, cmp);
for(int i = 1, st, dr; i <= n; ++i)
{
st = 0; dr = i;
while(dr - st > 1)
{
int mid = st + (dr - st + 1) /2;
if(p[mid].y <= p[i].x)st = mid;
else dr = mid;
}
if(st == 0)dp[i] = max(dp[i - 1],1LL * p[i].y - p[i].x);
else dp[i] = max(dp[i -1] ,dp[st] + p[i].y - p[i].x);
}
fout << dp[n];
return 0;
}