Pagini recente » Cod sursa (job #2477701) | Cod sursa (job #2482107) | Cod sursa (job #607346) | Cod sursa (job #2466663) | Cod sursa (job #3121286)
#include <bits/stdc++.h>
#define N 100005
#define mod 666013
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
int n,dp[N];
struct concert {
int st, dr;
}a[N];
bool cmp(concert A, concert B)
{
if (A.dr > B.dr) return 0;
if (A.dr < B.dr) return 1;
if (A.st < B.st) return 1;
return 0;
}
int Caut(int x)
{
int st = 1, dr = n, mij;
int k=0;
while (st <= dr)
{
mij = (st + dr) / 2;
if (a[mij].dr <= x)
{
k = mij;
st = mij + 1;
}
else
{
dr = mij - 1;
}
}
return k;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> a[i].st >> a[i].dr;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
{
int j = Caut(a[i].st);
dp[i] = max(dp[i - 1], dp[j] + (a[i].dr - a[i].st));
}
fout << dp[n];
return 0;
}