Pagini recente » Cod sursa (job #1073457) | Cod sursa (job #2592631) | Cod sursa (job #401178) | Cod sursa (job #2307750) | Cod sursa (job #474895)
Cod sursa(job #474895)
#include<fstream>
#include<algorithm>
using namespace std;
const char iname[]="heavymetal.in";
const char oname[]="heavymetal.out";
const int maxn=100005;
ifstream f(iname);
ofstream g(oname);
struct x
{
int x,y;
}a[maxn];
bool operator<(const x& a,const x& b)
{
return a.y<b.y;
}
int n,i,step,j,v[maxn],maxt;
int main()
{
f>>n;
for(i=1;i<=n;++i)
f>>a[i].x>>a[i].y;
sort(a+1,a+n+1);
for(i=1;i<=n;++i)
{
for(step=1;step<i;step<<=1);
for(j=0;step;step>>=1)
if(j+step<i&&a[j+step].y<=a[i].x)
j+=step;
v[i]=max(v[i-1],a[i].y-a[i].x+v[j]);
}
g<<v[n]<<"\n";
}