Từ Trường THPT chuyên Lương Văn Tụy, Ninh Bình
Thông tin
include<bits/stdc++.h>
using namespace std;
define int long long
define ii pair<int,int>
const int N=1e6+6; struct st { int x,y; }; int n,dp[N]; st a[N]; bool cmp(st a,st b) { if(a.x==b.x&&a.y<b.y) return a.y<b.y; else return a.x<b.x; } main() {
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+1+n,cmp);
int ma=0;
for(int i=1; i<=n; i++)dp[i]=a[i].y-a[i].x;
for(int i=1; i<=n; i++)
{
for(int j=1; j<i; j++)
{
if(a[j].y<=a[i].x)
{
dp[i]=max(dp[i],dp[j]+a[i].y-a[i].x);
}
else if(a[j].y>a[i].x)
{
dp[i]=max(dp[i],dp[j]+(a[i].y-a[j].y)-(a[j].y-a[i].x));
}
}
ma=max(ma,dp[i]);
}
cout<<ma;
}