Pagini recente » Cod sursa (job #105951) | Cod sursa (job #1570254) | Cod sursa (job #153087) | Cod sursa (job #1245013) | Cod sursa (job #2106262)
#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 i)
{
int p=1<<16,r=0;
while(p!=0){
if(fn[r+p]<=v[i].first && 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 k=cautare(i);
dp[i]=max(dp[i-1],dp[k]+v[i].second-v[i].first);
}
g<<dp[n];
return 0;
}