Pagini recente » Cod sursa (job #1317696) | Cod sursa (job #2987926) | Cod sursa (job #2315200) | Cod sursa (job #281521) | Cod sursa (job #2106290)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const int N=100001;
pair <int,int> v[N];
int n,dp[N],fn[N],m;
int cautare(int x)
{
int p=1<<16,r=0;
while(p!=0){
if(fn[r+p]<=x && r+p<=m)
r+=p;
p/=2;
}
return r;
}
int main()
{
f>>n;
for(int i=1;i<=n;i++){
f>>v[i].first>>v[i].second;
fn[i]=v[i].second;
}
sort(fn+1,fn+n+1);
sort(v+1,v+n+1);
int j,i;
for(i=2,j=1;i<=n;i++)
if(fn[i]!=fn[i-1])
fn[++j]=fn[i];
m=j;
for(int i=1;i<=n;i++){
int st=cautare(v[i].first);
int dr=cautare(v[i].second);
dp[dr]=max(dp[dr],dp[st]+v[i].second-v[i].first);
dp[dr]=max(dp[dr],dp[dr-1]);
}
g<<dp[m];
return 0;
}