Pagini recente » Cod sursa (job #317549) | Cod sursa (job #1305802) | Cod sursa (job #1206652) | Cod sursa (job #1279494) | Cod sursa (job #2111617)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");
const int N = 100001;
pair<long long, long long> v[N];
long long n, x[N], dp[N], k;
long long L = 16;
int binary_search(long long y)
{
int pas, r=0;
pas = 1 << L;
while(pas)
{
if(x[r + pas] <= y && r + pas <= k) r+=pas;
pas/=2;
}
return r;
}
int main()
{
int i, j;
fin>>n;
for(i=1; i<=n; i++)
{
fin >> v[i].second >> v[i].first;
x[i] = v[i].first;
}
sort(x + 1, x + n + 1);
sort(v + 1, v + n + 1);
//eliminare dubluri
for(i = 2, j = 1; i <= n; i++)
{
if(x[i] != x[i - 1]) x[++j] = x[i];
}
k = j;
for(int i = 1; i <= n; i++){
long long st=binary_search(v[i].second);
long long dr=binary_search(v[i].first);
dp[dr]=max(dp[dr], dp[st]-v[i].second + v[i].first);
dp[dr]=max(dp[dr],dp[dr-1]);
}
fout << dp[k] ;
return 0;
}