Pagini recente » Cod sursa (job #522641) | Cod sursa (job #930681) | Cod sursa (job #188753) | Cod sursa (job #2693436) | Cod sursa (job #516498)
Cod sursa(job #516498)
#include <fstream>
#include <algorithm>
using namespace std;
const char InFile[]="heavymetal.in";
const char OutFile[]="heavymetal.out";
const int MaxN=100111;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_inter
{
s_inter(int x2=0,int y2=0):x(x2),y(y2){}
int x,y;
};
struct cmp
{
inline bool operator() (const s_inter &a, const s_inter &b)
{
return a.y<b.y;
}
};
s_inter v[MaxN];
int N,best[MaxN];
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>v[i].x>>v[i].y;
}
fin.close();
sort(v+1,v+1+N,cmp());
for(register int i=1;i<=N;++i)
{
int p=1;
int u=i-1;
int sol=-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(v[m].y>v[i].x)
{
u=m-1;
}
else
{
sol=m;
p=m+1;
}
}
best[i]=max(best[sol-1],best[sol]+v[i].y-v[i].x);
}
fout<<best[N];
fout.close();
return 0;
}