Pagini recente » Cod sursa (job #2097706) | Cod sursa (job #1909091) | Cod sursa (job #1848367) | Cod sursa (job #1778259) | Cod sursa (job #1692220)
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int NMAX = 100005;
vector<PII> v;
int d[NMAX];
bool cmp(PII a, PII b){
return a.second<b.second;
}
int main(void) {
freopen("heavymetal.in","r",stdin);
freopen("heavymetal.out","w",stdout);
int n,a,b,m_ans=0;
scanf("%d",&n);
for(int i=0; i<n; ++i){
scanf("%d%d",&a,&b);
v.push_back(make_pair(a,b));
}
sort(v.begin(), v.end(), cmp);
for(int j,i=0; i<n; ++i){
if(i){
auto it = --upper_bound(v.begin(), v.end(), make_pair(v[i].first, v[i].first), cmp);
j=it-v.begin();
}
else
j=-1;
if(j>=0)
d[i]=max(v[i].second-v[i].first+d[j], m_ans);
else
d[i]=max(v[i].second-v[i].first, m_ans);
m_ans=max(d[i],m_ans);
}
printf("%d",m_ans);
return 0;
}