Pagini recente » Cod sursa (job #1277615) | Cod sursa (job #2338420) | Cod sursa (job #455520) | Cod sursa (job #2085747) | Cod sursa (job #1219643)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int nmax=100005;
int n,i,j,v[nmax],p;
struct spectacol {int bg,end;};
spectacol a[nmax];
bool cmp (spectacol A,spectacol B)
{
if (A.end!=B.end)
return A.end<B.end;
if (A.bg!=B.bg)
return A.bg<B.bg;
}
int binsearch (int val)
{
int step,rez=0;
for (step=1;step<=n;step<<=1);
for (rez=0;step;step>>=1)
if (rez+step<=n && a[rez+step].end<=val)
rez+=step;
return rez;
}
int main()
{
f>>n;
for (i=1;i<=n;i++)
f>>a[i].bg>>a[i].end;
sort(a+1,a+n+1,cmp);
v[1]=a[1].end-a[1].bg;
for (i=2;i<=n;i++)
{
p=binsearch(a[i].bg);
v[i]=max(v[i]-1,a[i].end-a[i].bg+v[p]);
}
g<<v[n];
return 0;
}