Pagini recente » Parcare2 | Monitorul de evaluare | Cod sursa (job #3309715) | Cod sursa (job #2446288) | Cod sursa (job #3315273)
#include <bits/stdc++.h>
#define pii pair <int, int>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int NMAX = 1e5 + 5;
bool cmp(pii x, pii y)
{
return x.second < y.second;
}
int n;
pii evenimente[NMAX];
long long dp[NMAX];
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> evenimente[i].first >> evenimente[i].second;
}
sort(evenimente + 1, evenimente + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int val = evenimente[i].first;
int l = 1, r = n, ans = 0;
while (l <= r)
{
int mid = (l + r) / 2;
if (evenimente[mid].second <= val)
{
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
dp[i] = max(dp[i - 1], dp[ans] + evenimente[i].second - evenimente[i].first);
}
fout << dp[n];
return 0;
}