Pagini recente » Cod sursa (job #2758942) | Cod sursa (job #2923151) | Cod sursa (job #108863) | Cod sursa (job #1274137) | Cod sursa (job #1151355)
#include <cstdio>
#include <vector>
#include <algorithm>
#define Nmax 100005
using namespace std;
struct nr
{
int a,b;
bool operator <(const nr &A) const
{
return b<A.b;
}
};
nr v[Nmax];
int t[Nmax],dp[Nmax];
int main()
{
int i,N,ind=0;
freopen ("heavymetal.in","r",stdin);
freopen ("heavymetal.out","w",stdout);
scanf("%d", &N);
for(i=1;i<=N;++i)
scanf("%d%d", &v[i].a,&v[i].b);
sort(v+1,v+N+1);
for(i=1;i<=N;++i)
{
while(ind<N && v[ind+1].b<=v[i].a)
++ind;
t[i]=ind;
}
for(i=1;i<=N;++i)
dp[i]=max(dp[i-1],dp[t[i]]+v[i].b-v[i].a);
printf("%d\n", dp[N]);
return 0;
}