Pagini recente » Cod sursa (job #270956) | Profil AnDrEwBoY | Cod sursa (job #1250180) | Cod sursa (job #442866) | Cod sursa (job #2764897)
//infoarema_Heavymetal
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct band {int lf, rg;};
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
int n, Optim[100002];
band B[100002];
int comparison (band x, band y)
{
if (x.rg < y.rg)
return 1;
return 0;
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
fin >> B[i].lf >> B[i].rg;
sort (B + 1, B + n + 1, comparison);
B[0].lf = B[0].rg = -1;
Optim[0] = 0;
for (int i = 1; i <= n; i++)
{
Optim[i] = Optim[i - 1];
int Left = 0, Right = i - 1;
while(Left != Right)
{
int m = (Left + Right + 1) / 2;
if (B[i].lf >= B[m].rg)
Left = m;
else
Right = m - 1;
}
if ((B[i].rg - B[i].lf + Optim[Left]) > Optim[i])
Optim[i] = B[i].rg - B[i].lf + Optim[Left];
}
fout << Optim[n];
fin.close();
fout.close();
return 0;
}