Pagini recente » Cod sursa (job #2181435) | Cod sursa (job #2208584) | Cod sursa (job #2629866) | Cod sursa (job #3260736) | Cod sursa (job #2047669)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#define NM 200005
#define pb push_back
#define x first
#define y second
#define mp make_pair
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,nor[NM],nrmact,dp[NM];
vector<int> srt;
vector<pair<int,int> > v;
pair<int,int> ult;
map<int,int> mm;
int main()
{
int a,b;
in>>n;
for(int i=1;i<=n;++i)
{
in>>a>>b;
srt.pb(a);
srt.pb(b);
v.pb(mp(b,a));
}
sort(srt.begin(),srt.end());
sort(v.begin(),v.end());
for(auto i:srt)
if(mm.find(i)==mm.end())
{
++nrmact;
mm[i]=nrmact;
nor[nrmact]=i;
}
for(int i=0;i<v.size();++i)
{
swap(v[i].x,v[i].y);
v[i].x=mm[v[i].x];
v[i].y=mm[v[i].y];
}
for(int i=1,ind=0;i<=nrmact;++i)
{
while(ind<v.size() && v[ind].y==i)
{
dp[v[ind].y]=max(dp[v[ind].y],dp[v[ind].x]+(nor[i]-nor[v[ind].x]));
++ind;
}
dp[i]=max(dp[i],dp[i-1]);
}
out<<dp[nrmact];
return 0;
}