Pagini recente » Cod sursa (job #12510) | Cod sursa (job #2609806) | Borderou de evaluare (job #2013263) | Cod sursa (job #487581) | Cod sursa (job #2540295)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("heavymetal.in");
ofstream cout ("heavymetal.out");
/*struct ura{
int x,y;
};
ura v[100005];*/
struct ura{
int x,y,tip,ind;
};
ura v[100005];
bool cmp (ura a,ura b)
{
int aa,bb;
if (a.tip==1)
aa=a.x;
else
aa=a.y;
if (b.tip==1)
bb=b.x;
else
bb=b.y;
if (aa<bb)
return true;
else
if (aa>bb)
return false;
else
if (a.tip<b.tip)
return false;
return true;
}
int dp[100005][2];
int main()
{
int n,sf,nr,i;
cin>>n;
for (i=1;i<=n;i++)
{
cin>>v[i*2-1].x>>v[i*2-1].y;
v[i*2-1].tip=1;
v[i*2].tip=2;
v[i*2-1].ind=v[i*2].ind=i;
v[i*2].x=v[i*2-1].x;
v[i*2].y=v[i*2-1].y;
}
sort (v+1,v+2*n+1,cmp);
int maxi=0;
for (i=1;i<=2*n;i++)
{
if (v[i].tip==1)
dp[v[i].ind][0]=maxi;
else
{
dp[v[i].ind][1]=max(maxi,v[i].y-v[i].x+dp[v[i].ind][0]);
}
maxi=max(maxi,dp[v[i].ind][1]);
}
cout<<maxi;
return 0;
}