Pagini recente » Cod sursa (job #3347442) | Cod sursa (job #634362) | Cod sursa (job #2867058) | Cod sursa (job #2446262) | Cod sursa (job #3347324)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
const int nmax=1e5;
int n, dp[nmax+5];
struct concert
{
int a, b;
};
vector<concert>v(nmax+5);
bool cmp(concert x, concert y)
{
return x.b<y.b;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].a>>v[i].b;
sort(v.begin()+1, v.begin()+n+1, cmp);
for(int i=1;i<=n;i++)
{
concert target;
target.b=v[i].a;
auto up=upper_bound(v.begin()+1, v.begin()+i, target, cmp);
int idx=up-v.begin()-1;
dp[i]=max(dp[i-1], (v[i].b-v[i].a)+dp[idx]);
}
cout<<dp[n];
return 0;
}