Pagini recente » Cod sursa (job #2481613) | Cod sursa (job #751871) | Cod sursa (job #146384) | Cod sursa (job #775948) | Cod sursa (job #487520)
Cod sursa(job #487520)
#include<fstream>
#include<algorithm>
#include<vector>
#define dmax 200004
using namespace std;
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
int n,mx,sol[dmax];
vector<int>v;
vector<int>::iterator it;
struct metal
{ int x;
int y;
int dif;
} k[dmax];
bool sf(const metal& a , const metal& b)
{ if(a.y != b.y)
return a.y < b.y;
return a.x <= b.x;
}
void norm()
{ int i;
sort(v.begin(),v.end());
unique(v.begin(),v.end()+1);
for(i=1;i<=n;i++)
{ it=lower_bound(v.begin(),v.end(),k[i].x);
k[i].x = it-v.begin();
it=lower_bound(v.begin(),v.end(),k[i].y);
k[i].y = it-v.begin();
mx=max(mx,k[i].y);
}
}
int main()
{ int i,j;
in>>n;
for(i=1;i<=n;i++)
{ in>>k[i].x>>k[i].y;
k[i].dif=k[i].y-k[i].x;
v.push_back(k[i].x);
v.push_back(k[i].y);
}
in.close();
norm();
sort(k+1,k+n+1,sf);
sol[1]=k[1].dif;
j=1;
for(i=1;i<=mx;i++)
{ sol[i]=sol[i-1];
while(k[j].y == i && j<n)
{ sol[i]=max(sol[i],sol[k[j].x]+k[j].dif);
j++;
}
}
out<<sol[mx];
out.close();
return 0;
}