Pagini recente » Cod sursa (job #515119) | Cod sursa (job #1542422) | Cod sursa (job #2893210) | Cod sursa (job #1412160) | Cod sursa (job #2506180)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5 + 5;
int n, dp[NMAX];
pair <int, int> a[NMAX];
int BinarySearch(int val)
{
int left = 1, right = n, mid, pos = 0;
while (left <= right)
{
mid = (left + right) / 2;
if (a[mid].second <= val)
{
pos = mid;
left = mid + 1;
}
else
right = mid - 1;
}
return pos;
}
int main()
{
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
fin >> n;
for (int i = 1;i <= n;++i)
fin >> a[i].first >> a[i].second;
sort(a + 1, a + n + 1, [&](pair <int, int> x, pair <int, int> y)
{
return x.second < y.second;
});
for (int i = 1;i <= n;++i)
{
int p = BinarySearch(a[i].first);
dp[i] = max(dp[i - 1], dp[p] + a[i].second - a[i].first);
}
fout << dp[n] << "\n";
fin.close();
fout.close();
return 0;
}