Pagini recente » Cod sursa (job #1447170) | Cod sursa (job #1133917) | Cod sursa (job #3163379) | Cod sursa (job #1472889) | Cod sursa (job #1897612)
#include <bits/stdc++.h>
#define y second
#define x first
typedef long long ll;
using namespace std;
ll N,D[100100];
pair<int,int> A[100100];
int caut(int x){
int st=1,dr=N;
while(st<dr-3){
int mid = (st+dr)/2;
if(A[mid].y<=x) st = mid;
else dr = mid;
}
for(;st<=dr;dr--) if(A[dr].y<=x) return dr;
return -1;
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ifstream cin("heavymetal.in");
ofstream cout("heavymetal.out");
cin >> N;
for(int i = 1,x,y;i<=N;i++){
cin >> x >> y;
A[i] = make_pair(x,y);
}
sort(A+1,A+1+N);
for(int i = 1;i<=N;i++){
int down = caut(A[i].x);
D[i] = A[i].y-A[i].x + (down > 0 ? D[down] : 0);
D[i] = max(D[i],D[i-1]);
// for(int j = 1;j<=N;j++) cout << D[j] << "\n "[j<N];
}
cout << D[N];
}