Pagini recente » Monitorul de evaluare | Monitorul de evaluare | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #3332245) | Cod sursa (job #3332244)
#include <fstream>
#include <algorithm>
#define int long long
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int Nmax = 1e5 + 5;
struct interval
{
int st, dr;
}v[Nmax];
bool cmp(interval a, interval b)
{
if (a.dr != b.dr)
return a.dr < b.dr;
return a.st < b.st;
}
int dp[Nmax];
int n;
int cb(int x, int i)
{
int st = 1, dr = i, ans = 0;
while (st <= dr)
{
int mid = (st + dr) / 2;
if (v[mid].dr <= x)
{
ans = mid;
st = mid + 1;
}
else
dr = mid - 1;
}
return ans;
}
signed main()
{
int ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i].st >> v[i].dr;
sort(v + 1, v + n + 1, cmp);
/*cout << '\n';
for (int i = 1; i <= n; i++)
cout << v[i].st << " " << v[i].dr << '\n';
cout << '\n';*/
for (int i = 1; i <= n; i++)
{
int j = cb(v[i].st, i - 1);
dp[i] = max(dp[i - 1], dp[j] + v[i].dr - v[i].st);
}
cout << dp[n];
}