Pagini recente » Development | Monitorul de evaluare | Monitorul de evaluare | infoarena - comunitate informatica, concursuri de programare | Cod sursa (job #3332245)
#include <fstream>
#include <algorithm>
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;
}
long long dp[Nmax];
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 n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> v[i].st >> v[i].dr;
sort(v + 1, v + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int j = cb(v[i].st, i - 1);
dp[i] = max((long long) dp[i - 1], (long long)dp[j] + v[i].dr - v[i].st);
}
cout << dp[n];
}