Pagini recente » Cod sursa (job #1052955) | Cod sursa (job #1951982) | Cod sursa (job #2618873) | Cod sursa (job #2786166) | Cod sursa (job #2549419)
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=100005;
ifstream fin ("heavymetal.in");
ofstream fout ("heavymetal.out");
struct interval
{
int x,y;
}v[nmax];
bool cmp(interval a,interval b)
{
return a.y<b.y;
}
int main()
{
int n,dp[nmax],rez=0;
fin >> n;
for (int i=1;i<=n;i++)
{
fin >> v[i].x >> v[i].y;
}
sort (v+1,v+n+1,cmp);
dp[n]=v[n].y-v[n].x;
for (int i=n-1;i>=1;i--)
{
dp[i]=v[i].y-v[i].x;
for (int j=i+1;j<=n;j++)
{
if (v[j].x>=v[i].y) dp[i]=max(dp[j]+v[i].y-v[i].x,dp[i]);
}
}
for (int i=1;i<=n;i++)
{
rez=max(dp[i],rez);
}
fout << rez;
}