Pagini recente » Cod sursa (job #2890254) | Cod sursa (job #1611506) | Cod sursa (job #797682) | Cod sursa (job #2559741) | Cod sursa (job #2539815)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
struct band{
int s,d,t;
}a[100009];
int n;
bool comp(band a, band b)
{
return a.s < b.s || a.s == b.s && a.d < b.d;
}
int BS(int s, int d, int index)
{
if(s > d)
return 0;
int mid = (s+d)/2;
if(a[mid].d <= a[index].s)
return max(a[mid].t, BS(mid+1, d , index));
else return BS(s, mid-1, index);
}
void Read()
{
int i,j;
int vmax = 0;
fin>>n;
for(i=1; i<=n; ++i)
{
fin>>a[i].s>>a[i].d;
}
sort(a+1, a+n+1, comp);
a[1].t = a[1].d - a[1].s;
for(i=2; i<=n; ++i)
{
int poz = BS(1, i-1 , i);
a[i].t = a[poz].t + (a[i].d - a[i].s);
}
for(i=1; i<=n; ++i)
if(a[i].t > vmax)
vmax = a[i].t;
fout<<vmax;
}
int main()
{
Read();
return 0;
}