Pagini recente » Cod sursa (job #1397270) | Cod sursa (job #2687062) | Cod sursa (job #2852082) | Cod sursa (job #1077269) | Cod sursa (job #2536107)
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
struct ura
{
int st,dr;
short fel;
int pz;
}v[200005];
bool cmp (ura a, ura b)
{
int pza;
if(a.fel==1)
pza=a.st;
else
pza=a.dr;
int pzb;
if(b.fel==1)
pzb=b.st;
else
pzb=b.dr;
return pza<pzb;
}
int dp[100005][2];
int main()
{
int mxc=0,n,m,i,j=0;
cin>>n;
for(i=1;i<=n;++i)
{
int a,b;
cin>>a>>b;
v[++j]={a,b,1,i};
v[++j]={a,b,2,i};
}
sort(v+1,v+2*n+1,cmp);
for(i=1;i<=2*n;++i)
{
if(v[i].fel==1)
dp[v[i].pz][0]=mxc;
else
dp[v[i].pz][1]=max(mxc,dp[v[i].pz][0]+v[i].dr-v[i].st);
mxc=max(mxc,dp[v[i].pz][1]);
}
cout<<mxc;
return 0;
}