Pagini recente » Cod sursa (job #3157024) | Cod sursa (job #1825415) | Cod sursa (job #1106330) | Cod sursa (job #2413535) | Cod sursa (job #2987992)
#include <bits/stdc++.h>
#define Android ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n, dp[100005];
struct vrajeala
{
int x, y;
bool operator < (const vrajeala A) const
{
if (y == A.y)
return x < A.x;
return y < A.y;
}
}a[100005];
void Test_Case()
{
int i, j, st, dr, mij, sol;
fin >> n;
for (i = 1; i <= n; i++)
fin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1);
for (i = 1; i <= n; i++)
{
st = 1;
sol = 0;
dr = i - 1;
while (st <= dr)
{
mij = (st + dr) / 2;
if (a[mij].y <= a[i].x)
{
st = mij + 1;
sol = mij;
}
else dr = mij - 1;
}
dp[i] = max(dp[i - 1], dp[sol] + a[i].y - a[i].x);
}
fout << dp[n];
}
int32_t main()
{
Android
int t;
t = 1;
while (t--)
Test_Case();
return 0;
}