Pagini recente » Cod sursa (job #56133) | Cod sursa (job #344601) | Cod sursa (job #2485125) | Cod sursa (job #618689) | Cod sursa (job #2027402)
#include <bits/stdc++.h>
#define a first
#define b second
using namespace std;
ifstream F("heavymetal.in");
ofstream G("heavymetal.out");
int n, st, dr, mij, Tm, x, y;
long long dp[1<<17];
//pair<int, int> p[100003], v[100003];
vector<int> w[1<<17];
int main()
{
/**
F >> n;
for(int i = 1; i <= n; ++ i) F >> p[i].a >> p[i].b, v[i]=p[i];
sort(v+1, v+n+1);
for(int i = 1; i <= n; ++ i)
{
st=1;dr=n;
while(st<=dr)
{
mij=(st+dr)>>1;
if(v[mij].a==p[i].a) {p[i].a=mij;break;}
else if(v[mij].a<p[i].a) st=mij+1;
else dr=mij-1;
}
st=1;dr=n;
while(st<=dr)
{
mij=(st+dr)>>1;
if(v[mij].b==p[i].b) {p[i].b=mij; w[mij].push_back(i);break;}
else if(v[mij].b<p[i].b) st=mij+1;
else dr=mij-1;
}
}
vector<int>::iterator it;
for(int i = 1; i <= n; ++ i)
if(w[i].size())
{
dp[i]=dp[i-1];dp1[i]=dp1[i-1];
for(it=w[i].begin(); it!=w[i].end();++it)
if(dp[*it]+1>dp[i]) dp[i]=dp[*it]+1, dp1[i]=dp1[*it]+v[i].b-v[i].a;
else if(dp[*it]+1==dp[i]&&dp1[*it]+v[i].b-v[i].a>dp1[i]) dp1[i]=dp1[*it]+v[i].b-v[i].a;
}
G << dp1[n];*/
F >> n;
for(int i = 1; i <= n; ++ i) {F >> x >> y, w[y].push_back(x); Tm=max(Tm, y);}
vector<int>::iterator it;
for(int i = 1; i <= Tm; ++ i)
{
dp[i]=dp[i-1];
for(it=w[i].begin(); it!=w[i].end();++it)
if(dp[i]<dp[*it]+i-(*it)) dp[i]=dp[*it]+i-(*it);
}
G<<dp[Tm];
return 0;
}