Pagini recente » Cod sursa (job #1746002) | Cod sursa (job #1785600) | Cod sursa (job #1342339) | Cod sursa (job #1535418) | Cod sursa (job #2303019)
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef long double ld;
const string file = "heavymetal";
const ll INF = 9223372036854775807ll;
const int inf = 2147483647;
struct ev{
int x, y;
bool operator<(const ev & obj)const{
if(y != obj.y)
return y < obj.y;
return x < obj.x;
}
};
ev v[100005];
int n, mx[100005];
int main()
{
ifstream fin (file+".in");
ofstream fout (file+".out");
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v+1, v+n+1);
mx[1] = v[1].y-v[1].x;
for (int i = 2; i <= n; ++i){
int st = 1, dr = i-1, m, ans = 0;
for (m = (st+dr)/2; st <= dr; m = (st+dr)/2)
if(v[m].y <= v[i].x){
ans = m;
st = m+1;
}else dr = m-1;
mx[i] = max(mx[i-1], mx[ans]+v[i].y-v[i].x);
}
fout << mx[n] << "\n";
return 0;
}