Pagini recente » Cod sursa (job #2800243) | Cod sursa (job #3031161) | Cod sursa (job #476990) | Cod sursa (job #1252592) | Cod sursa (job #2540799)
#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.d < b.d || a.d == b.d && a.s < b.s;
}
void Read()
{
int i,j;
int vmax = 0;
int dr, st, poz, mid;
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)
{
a[i].t = a[i-1].t;
st = 1;
dr = i;
poz = 0;
while(st<=dr)
{
mid = (st+dr)/2;
if(a[mid].d <= a[i].s)
{
poz = mid;
st = mid+1;
}
else dr = mid-1;
}
a[i].t =max(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;
}