Pagini recente » Cod sursa (job #860826) | Cod sursa (job #2106301)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("heavymetal.in");
ofstream g("heavymetal.out");
const long long N=100001;
pair <long long,long long> v[N];
long long n,dp[N],fn[N],m;
long long cautare(long long x)
{
long long 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].second>>v[i].first;
fn[i]=v[i].first;
}
sort(fn+1,fn+n+1);
sort(v+1,v+n+1);
long long 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++){
long long st=cautare(v[i].second);
long long dr=cautare(v[i].first);
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;
}