Pagini recente » Cod sursa (job #2853929) | Cod sursa (job #3031475) | Cod sursa (job #1731121) | Cod sursa (job #2648474) | Cod sursa (job #2801051)
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
long long n, dp[100001], limit;
pair<long long, long long> intervale[100001];
int binarySearch( int l, int r)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (intervale[mid].second <= limit)
{
if(mid + 1 > r)
{
return mid;
}
if(intervale[mid + 1].second > limit)
{
return mid;
}
else
{
return binarySearch(mid + 1, r);
}
}
else
{
return binarySearch(l, mid - 1);
}
}
return 0;
}
bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
int main()
{
intervale[0].first = intervale[0].second = 0;
dp[0] = 0;
in >> n;
for(int i = 1; i <= n; i++)
{
long long a,b;
in >> a >> b;
intervale[i] = {a,b};
}
sort(intervale + 1, intervale + n + 1, cmp);
dp[1] = intervale[1].second - intervale[1].first;
for(int i = 2; i <= n; i++)
{
limit = intervale[i].first;
dp[i] = max(dp[i],dp[i - 1]);
int poz = binarySearch(1, i - 1);
dp[i] = max(dp[i], dp[poz] + intervale[i].second - intervale[i].first);
}
out << dp[n];
return 0;
}