Pagini recente » Cod sursa (job #1423913) | Cod sursa (job #2806448) | Cod sursa (job #2732514) | Cod sursa (job #358772) | Cod sursa (job #2600363)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct intervale
{
int beg, endd;
}p[100002];
int n;
bool cmp(intervale A, intervale B)
{
if(A.beg < B.beg)
return 1;
else if(A.beg == B.beg)
if(A.endd < B.endd) return 1;
return 0;
}
int BS(int st, int dr, int nr)
{
int mij, poz;
while(st <= dr)
{
mij = st + (dr - st) / 2;
if(p[mij].endd <= nr)
{
poz = mij;
st = mij + 1;
}
else dr = mij - 1;
}
return poz;
}
int dp[100002];
int main()
{
int i, bss, j;
fin >> n;
for(i = 1; i <= n; i++)
fin >> p[i].beg >> p[i].endd;
sort(p + 1, p + n + 1, cmp);
dp[1] = p[1].endd - p[1].beg;
for(i = 2; i <= n; i++)
{
bss = BS(1, i - 1, p[i].beg);
dp[i] = max(dp[i - 1], dp[bss] + p[i].endd - p[i].beg);
}
fout << dp[n];
return 0;
}